[6주_5일차] 백준-1929 소수 구하기(Python)

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

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

 

 

 

 

<코드>

import sys
import math

input = sys.stdin.read
M, N = map(int, input().split())

# 에라토스테네스의 체를 사용한 소수 판별
is_prime = [True] * (N + 1)
is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님

for i in range(2, int(math.sqrt(N)) + 1):
    if is_prime[i]:
        for j in range(i * i, N + 1, i):
            is_prime[j] = False

# M 이상 N 이하의 소수 출력
for num in range(M, N + 1):
    if is_prime[num]:
        print(num)

<풀이과정>

-is_prime = [True] * (N + 1): N까지의 숫자를 소수로 가정하고 초기화

-is_prime[0] = is_prime[1] = False: 0과 1은 소수가 아니므로 False로 설정

-에라토스테네스의 체 적용:

-2부터 N의 제곱근까지 반복

-i가 소수인 경우, i의 배수들을 False로 설정

 

 

 

*에라토스테네스의 체 원리

1. 숫자 배열 생성: 2부터 N까지의 숫자를 나열
2. 소수 판별 시작: 배열의 첫 번째 숫자(2)를 소수로 간주하고, 그 배수들을 모두 삭제
3. 다음 숫자로 이동: 배열에서 지워지지 않은 다음 숫자를 소수로 간주하고, 그 배수들을 모두 삭제
4. 반복: 이 과정을 N의 제곱근 이하의 숫자에 대해 반복
5. 배열에서 지워지지 않은 숫자들이 모두 소수가 됨