[백준🥈3] #1929 소수 구하기 (Python)

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

문제

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

입력

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

출력

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

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

 

✔️ Code 

import sys
import time
input = sys.stdin.readline

m, n = map(int, input().split())
t = int(n**0.5)

arr = [True] * (n+1)
for i in range(2, t+1):
    if arr[i] == True:
        for j in range(i+i, n+1, i):
            arr[j] = False

for i in range(m, n+1):
    if i != 1 and arr[i] == True:
        print(i)

✏️ Comment

에라토스테네스의 체!! 미루고 미루다가 드디어 오늘 에라토스테네스의 체 개념을 공부해버리고야 말았다...이거 아니고선 시간초과가 나는 것 같았다 ^-^

어떤 수 n이 있다고 할 때, 2부터 n의 제곱근까지 중 작은 수들을 구해서 그 수들의 배수를 빼주는 방식이다. 체로 걸러내는 것 같다고 해서 에라토스테네스의 체라고 한단다.. 

처음에 arr = [True] * (n+1) 이렇게 n까지의 수를 다 True로 초기화해놓고, 2부터 n의 제곱근까지 돌면서 2를 제외한 2의 배수들을 다 False 처리 해주고, 3을 제외한 3의 배수들을 False 처리 해주고, 5를 제외한 5의 배수들을 False . .. . 이렇게 반복해가며 가장 작은 소수들의 배수를 다 없애버리는 거다. 그렇게 해서 마지막에 m부터 n까지 수 중에 True인 것만 출력하면 그게 답이다!