[백준] 1929번 소수 구하기

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

1929번: 소수 구하기

 

문제

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

 

입력

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

 

출력

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

 

 

풀이

소수를 구하는 대표적인 방법인 에라토스테네스의 체를 이용하여 구할 수 있다.

에라토스테네스의 체는 N까지 수 중에서 N의 제곱근 이하의 숫자의 배수를 지우는 것으로 소수를 구하는 방법이다.
N의 제곱근까지만 체크하는 이유는 N이 a와 b의 합성수라면 a와 b 둘 중 하나는 N의 제곱근 이하의 숫자이기 때문에 이미 체크가 되어 제거되었기 때문이다.

 

 

전체 코드

import sys
import math

START, END = map(int, sys.stdin.readline().split())
prime = [1 for _ in range(END+1)]
prime[1] = 0
size = int(math.sqrt(END))+1

for i in range(size):
    if prime[i] == 0 :
        continue
    for j in range(2, END+1):
        if i*j > END :
            break
        else:
            prime[i*j] = 0

for i in range(START, END+1):
    if prime[i] == 1:
        print(i)

 

코드로 구현하면 위와 같아 진다. 1은 소수도 합성수도 아닌 숫자이기 때문에 제거한다.
그 뒤 위에 서술한대로 N의 제곱근 이하인 동안 체크하면 된다.
END라는 범위가 있기 때문에 i*j가 END보다 커지는 경우에는 break하는 것으로 시간을 줄일 수 있다.