[파이썬/Python] 백준 1929번 소수 구하기

[파이썬/Python] 백준 1929번 소수 구하기

1929번: 소수 구하기

---

문제

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

입력

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

출력

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

예제 입력

3 16

예제 출력

3
5
7
11
13

풀이 1

import sys
import math

def is_prime(x):
    # 1은 소수가 아니므로 False 반환
    if x == 1:
        return False
    # x가 2부터 int(x의 제곱근)+1 까지의 수로 나누어떨어지면 소수가 아니므로 False 반환
    for i in range(2, int(math.sqrt(x)+1)):
        if x % i == 0:
            return False
    # 위의 조건에 해당하지 않으면 소수이므로 True 반환
    return True

# 입력받은 두 수의 범위를 저장
m, n = map(int, sys.stdin.readline().split())

# m부터 n까지의 수 중에서 소수인 수를 출력
for i in range(m, n+1):
    if is_prime(i):
        print(i)

이 코드의 실행 시간 복잡도는 O((n-m+1) * sqrt(n)) 이다.

현재 구현된 코드에서는 소수인지 판별할 숫자들을 하나씩 순회하면서 소수 여부를 판별한다. 이렇게 구현된 경우, 범위가 매우 큰 경우에는 많은 시간이 소요될 수 있다.

더 효율적인 방법은 에라토스테네스의 체(선형 시간 복잡도) 알고리즘을 이용하는 것이다. 에라토스테네스의 체 알고리즘은 2부터 시작하는 수열 중에서 소수인 수를 찾아내는 알고리즘이다. 아래는 에라토스테네스의 체 알고리즘을 이용한 코드 예시이다.

 

풀이 2

에라토스테네스의 체 알고리즘을 이용한 풀이

import sys

# n보다 작거나 같은 소수들의 리스트를 반환하는 함수
def get_primes(n):
    # 0과 1은 소수가 아니므로 False로 초기화
    is_prime = [False, False] + [True] * (n-1)
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            # i의 배수들을 모두 소수가 아닌 것으로 표시
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return primes

# 입력받은 두 수의 범위를 저장
m, n = map(int, sys.stdin.readline().split())

# n보다 작거나 같은 소수들의 리스트를 구함
primes = get_primes(n)

# m부터 n까지의 수 중에서 소수인 수를 출력
for p in primes:
    if p >= m:
        print(p)

이 코드는 get_primes 함수를 호출하여 n 이하의 소수들의 리스트를 미리 구해놓은 후, m 이상의 수 중에서 소수인 수를 찾아 출력한다. 이렇게 하면 소수를 찾아내는데 필요한 시간이 훨씬 적어져서 더 효율적인 코드가 된다.

 

에라토스테네스의 체 알고리즘을 이용한 이 코드의 시간복잡도는 O(nloglogn)이다. 이는 get_primes 함수에서 반복문을 n번 순회하고, 그 안에서 i의 배수들을 모두 검사하는데 필요한 반복문은 loglogn번 순회하기 때문이다. 이후 m 이상인 소수들을 출력할 때, 최악의 경우 n번을 순회하므로 전체적인 시간복잡도는 O(nloglogn + n) = O(nloglogn)이다.

 

참고자료

2. 소수 구하기 - 에라토스테네스의 체

Quiz) 에라토스테네스의 체 - 소수(Prime Number)를 찾아보자.