이번 문제는 백준 난이도 실버 3인 '소수 구하기' 문제이다.
https://www.acmicpc.net/problem/1929
이전에 풀었던 다음 소수문제와 다른 부분은 구간이 주어지고 구간 내 모든 소수를 구하는 것이다.
https://www.acmicpc.net/problem/4134
이번엔 다른 방식으로 '에라토스테네스의 체'를 사용해서 풀어볼 것이다.
에라토스테네스의 체란?
: 2부터 시작해, 어떤 수 n이 소수면 n제곱부터 n의 배수들을 False로 지정한다.
모두 처리하고 나서 True로 남은 인덱스들이 모두 소수로 남는 알고리즘이다.
이것 또한 √n 방식과 동일하게 √n +1 수까지만 반복해서 진행한다.
바로 코드로 설명을 진행하겠다.
[Python]
import sys
input = sys.stdin.readline
M, N = map(int, input().split())
일단 구간 M, N 이 입력된다.
prime = [True] * (N+1)
prime[0] = prime[1] = False
for i in range(2, int(N**0.5) + 1):
if prime[i]:
for j in range(i*i, N+1, i):
prime[j] = False
그리고 구간의 끝인 수의 크기만큼의 리스트를 생성한다. 리스트 값들은 모두 True로 초기화 해준다.
마찬가지로 0, 1은 소수가 될 수 없기 때문에 False로 지정
2부터 √n +1 까지 반복을 진행하는데
2는 소수이기 때문에 2의제곱인 4부터 N까지 2의 배수(i)들을 False로 바꾼다.
동일하게 3, 5 ... √n +1 이하의 소수까지 반복해서 처리한다.
그렇게 처리하고 리스트에 남은 값이 True인 인덱스들이 소수이다.
for i in range(M, N+1):
if prime[i]:
print(i)
출력해보면
3, 5, 7, 11, 13으로 잘 나오는 걸 알 수 있다.
이번 문제에서 핵심은 '에라토스테네스의 체'를 사용한 풀이라는 점!
외워두는 것이 좋을 것 같다!