[Algorithm] 에라토스테네스의 체 | 소수 찾기

소수를 찾는 방법 중 하나인 에라토스테네스의 체에 대해 알아보자

 

출처: https://ko.wikipedia.org/wiki/에라토스테네스의_체

 

원리는 다음과 같다.

 

💡 0부터 구하고자하는 수(n)까지 True로 채운 리스트를 생성한다.
💡 2를 제외한 2의 배수를 False로 바꾼다.
💡 3을 제외한 3의 배수를 False로 바꾼다.
💡 5를 제외한 5의 배수를 False로 바꾼다.
.
.
.
💡n의 최대 약수는 sqrt(n) 이하이므로 sqrt(n)의 배수를 모두 False로 바꾼다.
💡2~n까지의 숫자 중 True인 숫자들이 소수가 된다.

 

 

이를 코드로 구현하면 다음과 같다.

 

def isPrime(n):
	sieve = [True] * n
    
    # n의 최대 약수는 sqrt(n) 이하
    m = int(n ** 0.5)
    
    for i in range(2, m+1):
    	if sieve[i] == True: # i가 소수인 경우
        	for j in range(i+i, n, i): 
            	sieve[j] = False # i 이후 i의 배수는 소수가 아님
    
    # 2부터 n까지 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]