20. 소수 판별, 에라토스테네스의 체

  코드로 소수를 판별할 수 있는 방법은 다양합니다. 그 중에서 효과적인 방법인 에라토스테네스의 체에 대하여 설명하겠습니다.

 

  에라토스테네스의 체로 N까지의 소수를 확인하는 방법은 다음과 같습니다.

1. 2 ~ N까지의 모든 자연수를 나열한다.

2. 남은 수중 아직 처리하지 않는 수 i를 고른다.

3. i의 배수를 모두 제거한다.

4. 2, 3번 과정을 반복한다.

 

  여기서 i는 N의 제곱근 수 까지만 구해도, 소수 리스트를 만들 수 있습니다. 따라서 이를 파이썬 코드로 표현해 보자면

n = int(input()) # n 이하의 자연수 에서 소수 찾기

num = [True for i in range(n + 1)] # 소수 판단 bool list

for i in range(2, int(n**0.5) + 1): # 남은 수 중 아직 처리하지 않은 i
    if num[i] == True:
        j = 2
        while i*j <= n:
            num[i*j] = False # i의 배수 모두 제거
            j += 1
            
result = [i for i in range(2, n+1) if num[i]] # n보다 작은 소수 리스트