에라토스테네스의 체 🎻 (Sieve of Eratosthenes) - 백준 1929 python

👷‍♂️  소수(Prime Number) 판별 알고리즘이다.

소수  ?  1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

ex)  11은 약수가 1과 11 뿐이므로 소수가 맞지만,

       30은 1,2,3,5,6,10,15,30 이 약수로 1과 자기자신 뿐만아니라 다른 수도 약수로 가지므로 소수가 아니다. 

 

🚧  알고리즘

에라토스테네스의 체 = 소수 아닌 숫자를 걸러주는 체

소수가 아닌 수를 지워나가 소수만을 남게 한다.

출처 :  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부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

👩‍💻  파이썬 코드로 구현

문제 : M이상 N이하의 소수를 모두 출력하는 프로그램

입력: 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 입력 받음.

출력: 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

import sys

def sieve_of_eratosthenes(M,N):
	
    # 수를 담을 배열을 0으로 초기화
    prime=[0]*(N+1)
    
    # 2부터 N까지 수를 i번째 배열에 i 담기
    for i in range(2,N+1):
        prime[i]=i
	
    # 2부터 N까지 배열에서 0이면 건너뛰기 
    for i in range(2,N+1):
        if (prime[i] == 0):
            continue;
        # 자기자신을 제외한 소수의 "배수"를 지워나가기 위해, 2*i 부터 i만큼 증가하여 지워나감
        for j in range(2*i, N+1, i):
        	# 코드 상으로는 지운다는 것이 0으로 바꾼다는 것을 의미함.
            prime[j] = 0;
	
    # 0 으로 바뀌지 않은 수, 즉 소수를 출력함
    for i in range(M,N+1):
        if prime[i] != 0:
            print(prime[i])
            
def main():
    M, N = map(int, sys.stdin.readline().split(" "))
    sieve_of_eratosthenes(M,N)
   
main()