[알고리즘] 에라토스테네스의 체 (소수 구하기)

소수 구하는 코드를 짤라고 했는데 나는 정말 희한하게 짰다 (계산 복잡도 대단하게 짰다는 뜻)

😅 내 코드

start = int(input('시작 값 입력 (1보다 큰 값) : '))
end = int(input('끝 값 입력 : '))

li = []
nums = []

for num in range(start, end + 1):
    temp = li
    a = len(temp)
    for j in range(1, num + 1):
        if num % j == 0:
            li.insert(len(li), j)
    nums.append(li[a:])

result = []
for g in nums:
    if len(g) == 2:
        result.append(g[-1])
print(f'{start}~{end}까지의 소수 : {result}')

근데 이런 숫자를 직접 나누는 방식은 시간이 많이 소요되고,
특히 큰 숫자 범위에서는 더더욱 비효율적이라고 한다.

이럴 때 에라토스테네스의 체를 사용하면 시간 복잡도가 $O(n \log \log n)$로 매우 효율적으로 계산할 수 있음!

에라토스테네스의 체

임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법

체로 치듯이 수를 걸러낸다고 해서 에라토스테네스의 체라고 불림
2부터 시작해서 현재 수가 소수인지 확인하고,
만약 소수라면, 그 수의 배수들을 모두 지우는 방식으로 진행됨 (해당 수의 제곱부터 시작해서 배수들을 지우면 됨)

⭐ 프로세스

① 1부터 n까지 숫자를 쭉 쓴다.
② 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다.
③ 2를 제외한 2의 배수를 제거한다.
④ 3을 제외한 3의 배수를 제거한다.
※ 4의 배수는 제거할 필요가 없음 (2의 배수이므로)
⑤ 2, 3 다음으로 남아있는 가장 작은 소수, 즉 5의 배수를 제거한다.
⑥ 마지막으로, 7을 제외한 7의 배수까지 제거한다.

이 알고리즘에서 중요한 점은, 소수를 구할 때 특정 수의 배수들을 지울 필요가 있는지 여부를 판단하기 위해, 해당 수가 $\sqrt{n}$ 보다 큰 경우에는 이미 그보다 작은 소수들의 배수로 인해 지워졌다는 사실이다!
(= $\sqrt{n}$ 보다 작은 수의 배수만 지우면 된다는 뜻)

예)
$n = 100$ 이라면 $\sqrt{100} = 10$ 이므로,
11 이상의 소수의 배수는 이미 2, 3, 5, 7 등의 소수로 인해 지워진 것

⌨️ 에라토스테네스의 체

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1) 
    p = 2 # 현재 수 (i)
    while (p * p <= n): # 현재 수의 제곱이 최대값의 이하일 때
        if primes[p] == True: # 해당 인덱스의 값이 True 라면
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    return [p for p in range(2, n + 1) if primes[p]]

n = 30
print(sieve_of_eratosthenes(n))

# n -> 범위 최대값
# primes -> (n+1) 크기의 인덱스 (초기값은 True)

객꿀~