[백준 알고리즘/Python3] 1929 에라토스테네스의 체

문제이해

에라토스테네스의 체

 

 

에라토스테네스의 체에 대한 설명은 위키백과에도 잘 나와있다. 

-> https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

​

에라토스테네스의 체는 고전적인 방법이지만 소수 판정 알고리즘에서 빠질 수 없으며 소수를 이해하기 위한 최고의 알고리즘이라고 생각된다.

 

가볍게 설명하자면

• 1. 소수면 체크한다.
• 2. 체크한 값의 배수는 모두 소수판별에서 제외한다.
• 3. 이 과정을 반복한다.

 

 

 

 

코드

m,n = map(int, input().split())
count = 0
a = [False, False] + [True] * (n-1)

#에라토스테네스의 체로 리스트a를 조정한다.
for i in range(2, n+1):
    if(a[i]):
        
        for j in range(i*2, n +1, i):
            a[j] = False

#리스트a가 True일 때 인덱스를 출력
for i in range(m, n+1):  
    if(a[i]):
        print(i)

a리스트는 소수 판별을 위해 만들어진 리스트 입니다.

0,1은 판별하지 않으니 False로 둡니다.

 

a = [False, False] + [True] * (n-1)

들어오는 리스트의 갯수는 최대값인 n의 -1의 값입니다.

왜냐하면 총 0~n개의 원소를 가진 리스트를 만들어야 합니다 즉, n+1개의 리스트를 가져야 하죠

 

ex) n=16일 때 

총 배열 17개

 

n = 16일 때 앞에 False 2개를 안붙혔을 때 

총 배열 15개

 

15 + 2 해야 17이니 n-1 개를 생성 해줘야 합니다.

 

정리하자면

그냥 생성하면 16은 0~15 까지 생성할 것입니다.

 

앞에 2개가 있으니 +2를 해야할 것입니다.

(0~17) = 총 18개

 

0~16까지를 원하니 -1를 해야합니다.

 

 

#에라토스테네스의 체로 리스트a를 조정한다.
for i in range(2, n+1):
    if(a[i]):
        
        for j in range(i*2, n +1, i):
            a[j] = False

2부터 n까지 

 

• 만약 리스트의 값이 2이면
• 2의 배수부터 시작해서
• n까지 
• +i 하면서
• 리스트의 값을 False로 만듭니다.

 

#리스트a가 True일 때 인덱스를 출력
for i in range(m, n+1):  
    if(a[i]):
        print(i)

m부터 n까지 리스트의 값이 True라면 소수라는 뜻이니 출력하면 됩니다.