에라토스테네스의 체(Sieve Of Eratosthenes)

📔 에라토스테네스의 체(Sieve Of Eratosthenes) 란

• 대표적인 소수 판별 알고리즘 ( 소수: Prime Number )
• 한꺼번에 많은 숫자의 소수를 판별할 때 사용
• 숫자 한개의 소수를 판별하는 기본 소수 판별 알고리즘의 시간복잡도는 O(N)
• 하지만 수학적으로 접근해서 시간복잡도를 O(N^(1/2)) 까지 줄일 수 있다.
• 에라토스테네스의 체를 사용하면 시간복잡도는 O(n log log n)

📔 에라토스테네스의 체(Sieve Of Eratosthenes) 구현

• 자연수 50까지의 숫자 중에서 소수를 구한다고 생각해보자.
• 기본 알고리즘을 사용할 경우 O(N*N^(1/2)) 의 시간복잡도가 생긴다.
• 에라토스테네스의 체를 이용하여 구해보자.
• 먼저 51개의 값이 1(True)인 리스트를 만든다.
• for문으로 2부터 시작하여 자기 자신을 제외하고 자신의 배수의 숫자들은 0(False)로 만든다.
• 이미 자신이 0 이라면 건너뛴다.
• 리스트에서 값이 1인 인덱스를 추출하면 그 숫자들이 소수이다.

import math
import time


# 기본 소수 판별 알고리즘 O(N)
def prime(x):
    for i in range(2, x):
        if x % i == 0:
            return False

    return True


# 제곱근까지 O(N^(1/2))
def prime2(x):
    for i in range(2, int(math.sqrt(x))):
        if x % i == 0:
            return False

    return True


# 에라토스테네스의 체 O(n log log n)
def eratos(x):
    prime_number = [1] * (x + 1)
    for i in range(2, x):
        if prime_number[i] == 0:
            continue

        for j in range(i * 2, x + 1, i):
            prime_number[j] = 0


# 1부터 10000까지
n = 10000
print('기본')
start = time.time()
for k in range(2, n + 1):
    prime(k)
end = time.time()
print(f'시간: {end - start}')

print('제곱근')
start = time.time()
for k in range(2, n + 1):
    prime2(k)
end = time.time()
print(f'시간: {end - start}')

print('에라토스')
start = time.time()
eratos(n)
end = time.time()
print(f'시간: {end - start}')

'''
기본
시간: 0.3489978313446045
제곱근
시간: 0.012001991271972656
에라토스
시간: 0.0019986629486083984
'''