[알고리즘] 에라토스테네스의 체

출처 : https://www.google.com/url?sa=i&url=http%3A%2F%2Fm.blog.naver.com%2Fbyte93%2F221406082071&psig=AOvVaw2aE8Hrxec8sit4e7xihquc&ust=1680064651426000&source=images&cd=vfe&ved=2ahUKEwijsqDX5v39AhWnRvUHHTErCGsQr4kDegUIARDIAQ

소수의 정의

소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다.

2, 3, 5, 7, 11 등등

🧡 에라토스테네스의 체

• 특정 수가 주어질 때, 그 수 이하의 소수들 모두 뽑는 LOGIC~

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우 
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

최대 공약수 및 최소 공배수

뭐, 최대 공약수야 math 라이브러리에서 gcd사용해서 구하면 됌

최소 공배수는 두 수(a,b)의 최대 공약수를 각각 나눈 서로소와 최대 공약수의 곱으로 구할 수 있음 !

참고 블로그 : https://mathbang.net/204#gsc.tab=0

ETC - 서로소

서로소는 최대 공약수가 1인 두 자연수를 의미함

예를 들어, 2 - 3, 9 - 10, 4 - 5