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

 

 

백준 1929번: 소수 구하기

문제 바로 가기

---

📌 문제

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

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

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

 

 

 

📝 문제 접근 방법

 

문제 요약

• 주어진 범위 $[M, N]$ 에서 모든 소수를 찾아 출력합니다.
• 입력 범위는 최대 1,000,000까지 가능하므로 효율적인 소수 판별이 필요합니다.

 

아이디어

1. 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘

범위 내의 소수를 효율적으로 구하는 알고리즘으로
소수를 판별하는 데 불필요한 연산을 줄이기 위해 작은 소수의 배수를 반복적으로 제거하는 방식

• 작동 원리
  1. 초기화
     • 범위 $[2, N]$ 까지의 모든 수를 소수(True)로 가정합니다.
     • 특별히 0과 1은 소수가 아니므로 False로 설정합니다.
  2. 배수 제거
     • 2부터 시작하여, 현재 숫자가 소수(True)라면 그 배수들을 모두 제거합니다.
     • 배수 제거는 현재 수의 제곱부터 시작합니다.
       • 이유: 그 이전의 배수들은 이미 이전 단계에서 처리되었기 때문입니다.
     • 이 과정은 $\sqrt{N}$까지만 반복하면 됩니다.
       • 이유: 약수의 대칭적 관계 때문에 $\sqrt{N}$ 까지만 확인하면 모든 약수쌍을 파악할 수 있습니다.
  3. 결과 확인
     • 배수 제거가 끝난 후 리스트에서 True로 남아 있는 숫자들은 모두 소수입니다.

 

 

 

 

👩‍💻 나의 답안

import math

m, n = tuple(map(int, input().split()))

array = [True] * (n + 1)
array[0] = array[1] = False

for i in range(2, int(math.sqrt(n)) + 1):
    if array[i]:
        for j in range(i * i, n + 1, i):
            array[j] = False

for i in range(m, n + 1):
    if array[i]:
        print(i)

 

 

 

✨ 새로 알게 된 점

1. 에라토스테네스의 체

에라토스테네스의 체는 소수 판별에서 가장 효율적인 알고리즘 중 하나로, 소수의 배수를 제거하여 연산량을 줄이는 방식을 사용합니다. 특히 배수를 제거할 때 i * i부터 시작하는 이유는 그 이전의 배수는 이미 처리되었기 때문이며 약수의 대칭적 관계를 활용해 $\sqrt{N}$까지만 탐색하면 충분하다는 점도 알게 되었습니다. 또한 Python의 math.sqrt()를 사용해 제곱근을 계산하고 탐색 범위를 제한하는 방식으로 에라토스테네스의 체를 간단히 구현할 수 있음을 알았습니다. 이 알고리즘은 최대 범위가 1,000,000까지 주어지더라도 O(Nlog(log N))의 시간 복잡도로 효율적으로 동작한다는 점도 확인할 수 있었습니다.