에라토스테네스의 체 이론과 파이썬 구현

에라토스테네스의 체

에라토스테네스의 체는 소수를 판별하는 알고리즘으로 많은 소수를 구하거나 특정 범위의 소수를 구할 때 유용합니다.

 

n=100
a=[]

for i in range(2,n+1):
    for j in range(2,i):
        if i%j == 0:
            break
    else:
        a.append(i)

# 출력>>[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]
print(a)

기본적인 소수를 구하는 방법으로 특정 수보다 작은 모든 수로 나눠서 소수인지를 판단합니다.
위 방법은 정확하지만 범위의 소수를 모두 구할 때는 효율적이지 않습니다.

 

따라서 에라토스테네스의 체를 이용하면 시간을 줄이고 쉽게 소수를 구할 수 있습니다.

 

에라토스테네스의 체 알고리즘은

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.

2. 2부터 시작해서 나열된 수에서 지워지지 않은 수 중 가장 작은 2를 소수로 선택하고 2의 배수를 지웁니다.
3. 3도 지워지지 않았기 때문에 소수로 선택하고 3의 배수를 지웁니다.
4. 4는 지워졌기 때문에 넘어가고 5를 소수로 선택하고 5의 배수를 지웁니다.
5. 2, 3, 4와 같은 과정을 반복합니다.
6. 반복이 끝나면 지워지지 않은 수들을 소수로 출력합니다.

 

n=100
a=[True] * (n+1)
m = int(n ** 0.5)

for i in range(2,m+1):
    if a[i] == True:
        for j in range(i+i,n+1,i):
            a[j]=False

# 출력>>[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]
print([i for i in range(2, n+1) if a[i] == True])

에라토스테네스의 체를 이용한 방법입니다.
에라토스테네스의 체를 구할 때는 또한 n의 약수가 sqrt(n) 이하여서 sqrt(n)까지 검사하면 시간을 더 줄일 수 있습니다.
(sqrt는 루트)