문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
코드
import sys
import math
n, m = map(int,sys.stdin.readline().split())
arr = [True for i in range(m+1)]
for i in range(2,int(math.sqrt(m))+1):
if arr[i]==True:
j=2
while i*j <= m:
arr[i*j] = False
j+=1
for i in range(n,m+1):
if i>1 and arr[i]:
print(i)
풀이
데이터가 1,000,000 개 이하에서 여러 소수를 구하는 문제는 에라토스테네스의 체 알고리즘을 사용한다.
구해야하는 크기만큼의 True 배열을 만든다.
2부터 구해야하는 크기의 제곱근까지의 자기자신을 제외한 배수를 모두 False을 만든다.
2부터 2를 제외하고 4, 6, 8, 10... False
3부터 3을 제외하고 3, 6, 9, 12 ... False
...
이렇게 하고 True 인 것만 출력하면 소수만 나온다.
마지막에 출력 시, i는 2부터임을 주의하자.
'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
[백준] 1874 스택 수열 python (0) | 2022.02.18 |
---|---|
[백준] 2609 최대공약수와 최소공배수 python (0) | 2022.02.18 |
[백준] 1406 에디터 python (*) (0) | 2022.02.18 |
[백준] 10866 덱 python (0) | 2022.02.17 |
[백준] 10845 큐 python (0) | 2022.02.16 |