소수 구하기
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
코드
모든 숫자는 그 제곱근을 기준으로 약수의 절반이 각각 제곱근의 양옆에 위치하게 된다.
(ex - 16인 경우 1, 2, 4, 8, 16)그러므로 각 수마다 2부터(1은 어차피 약수이며 1은 소수가 아니다) 그 수의 제곱근(포함해야 한다-16의 경우 4도 약수이다)까지 반복해
만약 그 수가 나누어지면 소수가 아니고 제곱근까지 반복했음에도 나뉘어지지 않았다면 소수이다.
문제는 소수를 구하는 방법 중의 하나인 에라토스테네스의 체 알고리즘을 사용하여 풀이한다.
에라토스테네스의 체란?
임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른[2] 방법이다.
마치 체로 치듯이 수를 걸러낸다고 하여 불리는 이름.
- 알고리즘
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
- 2부터 시작해서 나열된 수에서 지워지지 않은 수 중 가장 작은 2를 소수로 선택하고 2의 배수를 지운다.
- 3도 지워지지 않았기 때문에 소수로 선택하고 3의 배수를 지운다.
- 4는 지워졌기 때문에 넘어가고 5를 소수로 선택하고 5의 배수를 지운다.
- 2,3,4와 같은 과정을 반복한다.
- 반복이 끝나면 지워지지 않은 수들을 소수로 출력한다.
풀이
M, N = map(int, input().split())
def prime_sieve(M, N):
N += 1
sieve = [True] * N # N개 만큼의 True값이 담긴 배열을 생성
for i in range(2, int(N**0.5)+1): # 2부터 N의 제곱근까지의 범위
if sieve[i]: # 에라토스테네스의 체 구현
for j in range(2*i, N, i):
sieve[j] = False # 소수가 아닌 수들은 False로 변환
for i in range(M, N):
if i > 1: # M값이 1이 될 경우를 대비하여 예외처리를 해준다.
if sieve[i]:
print(i)
prime_sieve(M, N)
- 주의할 점
테스트 케이스로 M에 1이 주어질 수 있는데, 기존 아레토스테네스의 체 함수는 입력값에 1이 올 수 없다는 걸 전제로 짜여지기 때문에 i가 1이 올 경우일 때를 위한 별도의 처리를 해주어야 한다.
네~