[Python][백준 1929] 소수 구하기

🔢 소수 구하기 문제 풀이

백준 1929번 소수 구하기 문제의 파이썬 풀이

📝 문제 설명

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

💡 풀이

이 문제는 에라토스테네스의 체 알고리즘을 사용하여 효율적으로 해결할 수 있다. 에라토스테네스의 체는 특정 범위 내의 모든 소수를 찾는 가장 효율적인 알고리즘 중 하나이다.

🔍 코드 설명

1. M부터 N까지의 수를 저장할 배열을 생성한다.
2. 2부터 N의 제곱근까지 순회하면서:
   • 현재 수가 지워지지 않았다면, 그 수의 배수들을 모두 지운다.
3. M부터 N까지 순회하면서 지워지지 않은 수(소수)를 출력한다.

✨ 참고

• math.sqrt()를 사용하여 제곱근을 구한다.
• 에라토스테네스의 체는 제곱근까지만 검사하면 된다.
• 배열에서 0은 지워진 수를 의미한다.

🎯 주의사항

• 1은 소수가 아니다.
• 메모리 사용량을 고려해야 한다.
• 시간 복잡도는 $O(NloglogN)$이다.

🚀 다른 풀이 방법

불리언 배열을 사용한 방법:

import sys

def sieve(m, n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i + i, n + 1, i):
                is_prime[j] = False
    
    for i in range(m, n + 1):
        if is_prime[i]:
            print(i)

m, n = map(int, sys.stdin.readline().split())
sieve(m, n)

---

📝 코드

import sys
import math

m, n = map(int, sys.stdin.readline().split())
A = [0] * (n + 1)

for i in range(2, n + 1):
    A[i] = i

# 에라토스테네스의 체
for i in range(2, int(math.sqrt(n)) + 1):
    if A[i] == 0:
        continue
    for j in range(i + i, n + 1, i):
        A[j] = 0

for i in range(m, n + 1):
    if A[i] != 0:
        print(A[i])

Python Coding Test 카테고리 내 다른 글 보러가기