[백준 1929] 소수 구하기 (파이썬 풀이)

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

문제

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

입력

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

출력

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

예제 입력 1 

3 16

예제 출력 1 

3
5
7
11
13

제출 코드 1

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
for i in range(n,m+1):
    if i==1:
        continue
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            break
    else:
        print(i)

1은 소수가 아니니 제외한다.

숫자의 약수는 대칭이기 때문에 해당 수의 제곱근까지만 계산해주면 된다.

예를 들어 12의 약수는 1, 2, 3, 4, 6, 12인데 (1,12), (2,6), (3,4), (4,3), (6,2), (12,1) 이런식으로 대칭이다.

range(2, int(i**(1/2))+1)

i%j==0로 나누어떨어지면 소수가 아니므로 for문을 멈춘다.

만약 for문을 다 통과하고 i가 1이 아니면 해당 숫자를 출력한다. (for-else 문)

제출 코드 2 (에라토스테네스의 체)

n,m = map(int, input().split())
m += 1
isprime = [True] * m
for i in range(2, int(m**(1/2))+1):
    if isprime[i]:
        for j in range(2*i, m, i):
            isprime[j] = False
for i in range(n,m):
    if i>1 and isprime[i]:
        print(i)

에라토스테네스의 체란?

고대 그리스의 수학자 에라토스테네스가 만든 소수 판별 알고리즘. 마치 체로 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

출처:위키백과

1. 2부터 정해진 범위까지 수를 나열한다.

2. 2는 소수이므로 2와 자기자신을 제외한 2의 배수는 다 지운다. (빨간색)

3. 남아있는 수 가운데 다음 소수는 3이므로 3과 자기자신을 제외한 3의 배수는 모두 지운다. (초록색)

4. 남아있는 수 가운데 다음 소수는 5이므로 5과 자기자신을 제외한 5의 배수는 모두 지운다. (파란색)

5. 위 과정을 반복하면 결국에는 소수만 남는다.

에라토스테네스의 체를 사용하면 모든 수를 검사할 필요가 없으므로 시간복잡도가 O(N)에서 O(N^(1/2))로 감소한다. 에라토스테네스의 체로 푼 코드가 압도적으로 시간이 적게 들었다. 에라토스테네스의 체는 자주 사용되는 알고리즘이기 때문에 꼭 알아두자.