에라토스테네스의 체 - 소수를 구할때

코딩테스트에서 소수에 관련된 문제가 은근히 많이나온다.

for 문을 2번돌려 일일이 약수를 비교해 구면 쉽겠지만, 숫자가 커지면 엄청나게 많은 시간 O(n^2)이 걸려 시간초과로 실패한다.

하지만 에라토스테네스의 체 알고리즘을 사용하게 된다면 O(NlogN)만에 소수를 구할 수 있다.

N=50 이하의 소수들을 구할때 에라토스테네스의 체 알고리즘을 사용하면 이렇다.
(1은 소수가 아니니 처음부터 제외한다.)
# 숫자 A가 어느 숫자의 배수라는 것은 A가 소수가 아님을 생각하면 된다.

i=2일때, 2를 제외한 50이하 사이에서 2의 배수들을 제외시킨다.
2 다음으로 제외되지 않은 숫자는 3,
i=3일때, 3를 제외한 50이하 사이에서 3의 배수들을 제외시킨다.
3 다음으로 제외되지 않은 숫자는 5,
i=5일때, 5를 제외한 50이하 사이에서 5의 배수들을 제외시킨다.
5 다음으로 제외되지 않은 숫자는 7
i=7일때, 7을 제외한 50이하 사이에서 7의 배수들을 제외시킨다.

8^2 > 50이므로 8보다 작은 수중에서 소수의 배수만 지워도 충분하다.
즉, 50 이하의 수 가운데, 2, 3, 5, 7의 배수를 지우고 남은 수는 모두 소수다.

이해가 가지 않을때 직접 그려서 알고리즘을 적용해보면 좋다.

Python으로 작성한 에라토스테네스를 이용한 소수구하기

N=50
prime_check=[0] * N # 인덱스 n은 숫자n이 소수인지 판별 하는용도. 소수면 0, 소수가 아니면 1로 한다.

for i in range(2,int(N**0.5)+1):
	if(prime_check[i]==0): # i가 소수일때
    	for j in range(i+i, N, i): # i를 제외한 N이하 i의 배수들을
        	prime_check[j]=1 # 1로 바꾸어 소수가 아님을 체크해준다.

# 소수 출력하기
for j in range(2, len(prime_check)):  
	if(prime_check[j]==0): #j가 n일때 0이면 n이 소수이므로 j를 출력해준다
    	print(j)