[알고리즘]소수탐색: 에라토스테네스의 체

소수를 구하는 알고리즘의 경우 다양하게 존재합니다. 

그러나 N개의 숫자에 대해서 소수인지 판별하는 경우 N의 복잡도를 가지더라도

이를 N번 반복하게 되면 결국 $O(N^2)$의 시간복잡도를 나타내게 됩니다. 

 

이런 경우 시간초과를 피하면서 문제를 해결하기 위해 에라토스테네스 체를 이용해야합니다. 

 

N의 갯수를 가지며 , 모든 인덱스(인덱스는 숫자의 값을 의미합니다)에 대해 True의 값을 가지는 배열을 생성해줍니다 

여기서 True의 의미는 소수를 의미합니다. 

ex) 생성한 배열 arr에서 arr[2]=>True라면 index는 2이므로 2는 소수라고 판단하는 것입니다. 

 

초기에는 모든 숫자를 소수라고 가정하고 시작합니다. 

 

소수의 정의는 1과 자기자신을 제외하고 나누어떨어지지 않는 수이기 때문에 

임의의 인덱스 i의 원소가 True라면 i의 배수에 해당하는 인덱스를 가지는 원소는 전부 False로 업데이트를 해줍니다.

 

예를들어 index 2를 가지는 원소는 True이므로 배수 4,6,8,.....2n의 인덱스를 가지는 원소를 모두 Fasle로 바꿔줍니다 

그림으로 보면 아래와 같습니다. 

 

 

 

 

코드구현 

코드로 보면 다음과 같습니다. 

 

1.전체 범위에 대해 True값을 가지는 배열을 생성하여 줍니다. 

2.반복문을 통해 i번째 원소가 True라면 2i,3i.....ni까지 False로 업데이트를 진행해줍니다 

 

def prime_sieve(M,N):
#먼저 전체 범위에 대해서 True인 배열을 만들어줍니다 
    arr =[True for i in range(N+1)]
    arr[0], arr[1]=False, False
    for i in range(2,N+1):
        if arr[i]==True:
#예를들면 2의 경우 4,6 ..등등의 배수 관계에 있는 숫자들은 소수가 아니므로 
#False로 업데이트를 해줍니다 
            j=2
            while i*j<N+1:
                arr[i*j]=False
                j+=1
    return arr