[Python] 에라토스테네스의 체

에라토스테네스의 체

에라토스테네스의 체는 코딩테스트에서 소수를 구할 때 시간을 많이 줄일 수 있는 대표적인 소수 판별 알고리즘이다.
소수란 양의 약수를 두 개만 가지는 자연수를 의미하며 이러한 소수를 빠르고 정확하게 구하는 방법이 에라토스테네스의 체이다.

1) 2부터 시작해 제곱을 찾은 후 2씩 증가시키고 찾은 수들을 True 처리

2) 3부터 시작해 제곱을 찾은 후 3씩 증가시키고 찾은 수들을 True 처리

3) 4부터 시작해 제곱을 찾은 후 4씩 증가시키고 찾은 수들을 True 처리

4) 1~3을 목표치까지 반복

prime=[True] * 10001
prime[0]=False
prime[1]=False
for i in range(2,10001):
    if prime[i]==True:
        for j in range(i*i,10001,i):
            prime[j]=False

다른 방법으로는

check = [False] * (10001)
primes = []
for i in range(2,10001):
    if check[i]:
        continue
    j = i*2
    primes.append(i)
    while j <= n:
        check[j] = True
        j += i