백준 1929번 "소수 구하기"
Question:
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
Input:
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다.
(1 ≤ M ≤ N ≤ 1,000,000)
M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
Output:
한 줄에 하나씩,
증가하는 순서대로 소수를 출력한다.
Restriction:
시간제한:
2 초
Example Case:
Input case 1:
3 16Output case 1:
3
5
7
11
13풀이 과정:
이 문제는,
소수를 구하는 알고리즘인
“에라토스테네스의 체”를 이용한 문제이다.
에라토스테네스의 체 알고리즘은 특정 범위 내
소수들을 대량으로 빠르게 판별하는 알고리즘이다.
단일 원소에 대해
소수를 구하는 방법은
수를 입력받은 후
2부터 N-1까지의 수로 나누어 지는지
모든 경우의 수를 확인하는 법이 있다.
그러나 위 방법의 경우 O(N^2)으로 시간이 많이 걸린다.
에라토스테네스의 체 같은경우 O(Nlog(logN))의 시간으로 가장 빠르다.
에라토스테네스의 체 구현하기
Q. 1 부터 N까지의 수 중 소수를 구하고 싶다.
1.1 부터 N까지의 수를 가상의 배열에 둔다
2.1은 제외하고,2부터 2의 배수에 관해 수를 지워나간다.
3.그 다음 수인 3에도 똑같이 적용한다.
4.이미 지워진 수는 제외하고 계속 제외하면 남는 수가 소수이다.
이 알고리즘은
소수가 아닌 수들은 반드시 다른 소수로 나누어진다는 것에 기반을 둔다.
다만,최적화를 위해 코드상에서
중복되는 수 삭제를 최소화하기 위해 제곱 수부터 시작하여
소수가 아닌수에 해당하는 수를 삭제한다.
또한,
소수 판별 범위를
N의 제곱근까지의 범위내까지 검사한다.
이는,N의 최대 약수는 N의 제곱근 이하임으로,
이 또한 최적화의 일부이다.
추가로, 문제의 조건에 따라
return문을 살펴보면
A부터 B까지의 소수인 수들을 return 하고 있다.
출력부분도 한줄씩 출력하는 출력문이다.
아래는 python으로 작성한 소스코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import sys
M,N = map(int,sys.stdin.readline().split())
def solve(A,B):
sieve = [False,False] + [True] * (B-1) # 0,1은 소수가 아니기에 패스
m = int(B ** 0.5) #루트 근 까지의 범위 내(최적화)
#B의 최대 약수가 sqrt(B) 이하임으로, i = sqrt(B)까지 검사
for i in range(2, m + 1):
if sieve[i] == True: #소수 판별
for j in range(i*i , B+1 , i): #중복제거 최적화,제곱 범위
sieve[j] = False #배수 지우기
return [i for i in range(A,B+1) if sieve[i] == True]
[print(i) for i in solve(M, N)] #한줄씩 출력