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

에라토테네스의 체

소수를 구하는 방법은 여러가지가 있다. 그중에서도 에라토테네스의 체라는 방법에 대해서 소개해 볼까 한다.

에라토테네스의 체는 대량의 소수를 한번에 구할때 유리하다.

에라토테네스의 기본 아이디어는 배열을 만든 다음 index값을 수 라고 생각한다. 그 다음 소수인 수에 대해서만 체크를 하지 않으면 됩니다.(저의 경우엔 False를 해당 인덱스에 값으로 넣었습니다.)

직접 짠 코드를 보면서 설명하면 좋을 것 같습니다.

전체 코드는 이러합니다. input값으로 주어지는 수는 N>=1 인 자연수로 가정했습니다.

wholelist=[False,False]+[True]*(b-1)

#어떤 값의 약수중 제일 작은 값은 sqrt(N) 보다 같거나 작다.
n=int(b**0.5)+1
for i in range(2,n):
    if (wholelist[i]==True):
        for j in range(2*i,b+1,i):
            wholelist[j]=False





for k in range(a,b+1):
    if wholelist[k]==True:
        print(k)

첫번째 부분입니다.

wholelist=[False,False]+[True]*(b-1)

여기 보면 에라토네스의 체 기본 원리인 배열 생성이 나와 있습니다. 저의 경우 “인덱스”를 기준으로 하여 수를 생각했습니다. 파이썬의 경우 인덱스의 시작은0 이죠. 그래서 첫번째 원소는 무조건 False입니다.

또한 1도 무조건 소수가 아닙니다. 소수의 정의는 여기서 다 하지는 않겠습니다. 2는 무조건 소수입니다. 그래서 True입니다. 2 이상의 수는 일단 무조건 True를 default값으로 저장합니다.

두번째 부분입니다.

#어떤 값의 약수중 제일 작은 값은 sqrt(N) 보다 같거나 작다.
n=int(b**0.5)+1
for i in range(2,n):
    if (wholelist[i]==True):
        for j in range(2*i,b+1,i):
            wholelist[j]=False

여기서 조금 수학이 들어갑니다. 만약 input 값이 합성수 (소수가 아닌 수)이면 약수중 하나는 무조건 n**(1/2) 보다 작거나 같습니다. 따라서 루트 n까지만 약수인지 확인하면 소수임을 증명할 수 있습니다.

이 결과에 때문에 시간 복잡도는 O(n**1/2)이 됩니다. 개이득! 여기서 0.5 제곱해주고 자료형의 반올림 현상때문에 문제가 생길까봐 +1까지 더해줍니다. 그래서 2부터 루트 n까지 돌면서 해당하는 인덱스가 True이면 초기 input값인 b까지 모든 배수들을 True로 바꿔줍니다.

마지막 출력입니다.

for k in range(a,b+1):
    if wholelist[k]==True:
        print(k)

자기가 원하는 구간의 소수를 이러면 다 구할 수 있습니다.

이상 에라토네스의 체에 대한 설명이었습니다.