[백준 1929] 기본 수학 2 - 소수 구하기 (에라토스테네스의 체)

문제

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

입력

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

출력

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

예제 입력

3 16

예제 출력

3 5 7 11 13

 

 

풀이

 

소수를 구해야하는 범위가 큰 문제로,

성능을 고려하지 않는다면 시간 초과가 뜰 것이다.

 

따라서 문제에서 제시한 에라토스테네스의 체를 통해 문제를 풀어야 한다.

 

출처 - 위키백과

에라토스테네스의 체는 미리 주어진 숫자 목록에서 작은 수부터 소수인지 판별하여

그 수가 소수이면 배수의 수들을 모두 제거한 뒤 남은 수들을 차례로 세어 나가는 방법이다.

 

보통 구할 범위 마지막 수의 제곱근 보다 작은 숫자 만큼만 소수를 판별해주면

나머지는 모두 소수이다. (그림의 경우 120이니, 10 까지만 판별해주면 된다.)

 

m,n = map(int,input().split())

a=[i for i in range(n+1)]
for i in range(2, int(n**0.5)+1):	# 마지막 숫자의 제곱근 이전까지만 판별
    for j in range(i+i, n+1, i):	# 숫자의 배수들 제거
        a[j]=0
for i in a:
    if i >=2 and i>=m:
        print(i)

 

2021-09-15 수정

 

배수를 제거할 때, for문보다 슬라이싱을 활용하는 방법이 훨씬 성능이 좋다.

 

m,n = map(int,input().split())

a=[False,False] + [True for i in range(n-1)]
for i in range(2, int(n**0.5)+1): # 마지막 숫자의 제곱근 이전까지만 판별
    a[i*2::i] = [False]*((n-i)//i) # 숫자의 배수들 제거
        
for i in range(m,n+1):
    if a[i]:
        print(i)