[수학] 에라토스테네스의 체

대량의 소수를 빠르게 찾는 알고리즘

개념

n까지의 소수를 구할 때, 리스트에 2~n까지 저장한 후 2의 배수, 3의 배수, 5의 배수, ... i의 배수를 제외시키면 소수만 남게 된다.
여기서 i의 값은 리스트에 남은 순차적인 값들이다.

예시

코드(python)

n = 120
prime = [i for i in range(2, n+1)]

for i in prime:
    num = 2
    while i * num <= n:
        if i * num in prime:
            prime.remove(i * num)
        num += 1

print(prime)	
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]