[Python] n까지의 소수 구하기 - 에라토스테네스의 체

1. 기본

1. 2부터 구하고자 하는 수까지 모두 나열

2. 2부터 숫자를 올리며 자신의 배수는 제거

3. 과정 2를 반복하면 구간의 모든 소수가 남게 됨

2번에서 올라가는 숫자는 구하고자 하는 수까지 가지 않아도 된다. 구하고자 하는 수의 제곱근까지만 가도 됨.

2. 구현

# 정수 n까지의 소수 리스트 얻기
def sieve_of_eratosthenes(n):
    prime = [True] * (n + 1)
    prime[0] = False
    prime[1] = False

    for p in range(2, int(n**0.5) + 1):
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False

    return [p for p in range(2, n + 1) if prime[p]]

print(sieve_of_eratosthenes(n))

1. 외부 반복문의 상한을 sqrt(n)으로 설정하는 이유

- 합성수(1과 자기 자신을 제외한 약수가 있는 수)는 반드시 a * b 로 쪼갤 수 있다.

- 이 때, a와 b중 한 값은 반드시 sqrt(n) 미만이다. 그렇지 않다면 a*b 는 항상 a*b>=n 이 되므로 모순이 발생한다.

- 따라서, sqrt(n) 까지만 확인해도, 이보다 큰 값은 이미 더 작은 소수의 배수에서 걸러졌기 때문에 생각하지 않아도 무방하다.

 

2. 내부 반복문 : p*p에서 시작하는 이유

- p^2 보다 작은 p의 배수는 이전 단계에서 이미 처리되었다.

- 예를 들어 p=5 일 때, 10, 15, 20 등의 값은 이미 2 의 배수에서 10, 20 이 처리되었고, 3 의 배수에서 15 가 처리됐다는 의미이다. 따라서 p^2 에서 시작할 수 있다.

- 참고) 이 방법까지 쓸 경우 𝑂(𝑙𝑜𝑔(𝑙𝑜𝑔(𝑛))O(log(log(n)) 까지 줄일 수 있다고 한다.

 

2.1. 시간복잡도 계산하기

- 시간 복잡도와 관련, 잘 모르겠는 부분이 있어 Claude AI에게 물어봤다.

- 둘 모두 급수의 합을 다루기 때문에, 뭔 소린가 싶으면 그냥 이렇구나 하고 보고 넘어가자.

- 요약하면 외부 반복문에서 sqrt(n) 까지만 소수의 탐색을 진행했을 때, 내부 for문의 범위에 따른 시간 복잡도는 아래와 같단다.

- 2p에서 시작 : O(n log n)

- p*p에서 시작 : O(n(log(log(n)))

 

2.1.1. 2p에서 시작하기

- 2p 에서 시작해 n 까지 p의 배수는 n/p 개이다.(O(n))을 보고 있으므로 -1 같은 사소한 건 재끼자) - 예를 들어 2 의 배수는 4, 6, 8, ... , n = n/2 - 3 의 배수는 6, 9, ..., n = n/3

- (몰라도 됨) 일반적으로 소수의 개수는 n/ln(n) 개로 알려져 있다(소수 정리)- 여기서는 간단하게, p 부터 sqrt(n) 까지의 모든 소수의 배수의 개수를 세보자

n * (1/2 + 1/3 + 1/5 + ... + 1/sqrt(n))

- 위 괄호 내 식은 조화급수 H(n) = (1 + 1/2 + 1/3 + 1/4 + ...) 와 유사하다. 실제로는 더 작다.

- 이 때, 조화급수의 값은 log n + gamma 와 유사하다고 알려졌다. gamma 는 상수니까 몰라도 됨.

- 그런 유사성으로 접근했을 때, 위의 식은 n * H(sqrt(n)) 이라는 값이 된다. - 이는 n/2 * log(n) 이고, - Big O로 쓰면 O(n(log(n))) 이 된다.

2.1.2. p*p에서 시작하기

- 위와 같은 논리로, 여기서는 n까지의 p의 배수 중, p*p까지의 p의 배수를 뺀 값이 된다.

- p^2에서 시작해 n까지 이어지는 p의 배수의 개수는 (n-p^2) / p = n/p^2 - 1 이 된다.

- 또, 마찬가지로 2부터 sqrt(n) 까지의 모든 소수에 대해 계산해보면 아래처럼 나온다.

n * ( 1/2^2 + 1+3^2 + 1+5^2 + ... + 1+( sqrt(n))^2) ) - (sqrt(n) - 1)

- 여기서 n과 곱해진 괄호 부분은 basel 문제로 알려져 있다. 1/1^2 + 1/2^2 + ... + 1+n^2 의 값이 파이 제곱을 6으로 나눈 값에 수렴한다고 알려져 있는데, 2p의 케이스와 마찬가지로 실제 값은 더 작을 것이다.

- 중요한 건, n과 곱해진 값을 상수 C로 근사할 수 있게 된다는 것이다. 따라서 위 식은

n * C - (sqrt(n) - 1)

으로 쓸 수 있다. 이는 상한값이며, 실제 시간 복잡도는 더 수학적으로 파고들면 O(log(log(n)))까지 나온다고 한다.