에라토스테네스의 체

1. 에라토스테네스의 체: 2부터 배수들을 지워나가며 지워지지 않은 제일 처음 수가 소수가 되고, 또 그 소수의 배수를 지워나가며 소수를 찾는 방법

 

2. 1부터 N까지 소수가 몇개인지 판별하는 방법

 2-1 약수가 있는지 확인해서 끝까지 조사해서 없으면 소수( 시간 복잡도: O(N^2) )

 2-2 √N까지만 조사해서 없으면 소수( 시간 복잡도: O(NlogN) )

 

 2-3 에라토스테네스의 체 이용( 시간 복잡도: O(Nlog(logN)) )

 

3. 에라토스테네스를 활용해, 소수 구분하는 동작 순서

 

1) 2부터 N까지 모든 정수를 적음

2) 아직 지우지 않은 소수 중 가장 작은 소수를 찾음(이 수를 P라고 함)

3) 아직 지우지 않은 수들 중, P의 배수를 크기 순서대로 지움

4) 아직 모든 수를 지우지 않았다면 2) 단계로 돌아감.

 

 

 

코드 구현:

#2부터 N까지 True인 boolean 배열 생성
is_prime = [True] * (N - 1) 

for i in range(2, N+1):
	#아직 지우지 않은 수 중 가장 작은 소수를 찾음
    if is_prime[i]:
    	for j in range(i * 2, N + 1, i):
        	#j가 소수가 아님을 is_prime 배열에 체크
        	if is_prime[j]: 
            	is_prime[j] = False