[백준/파이썬] 1929번 소수 구하기 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 1929번 소수 구하기
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. (1 ≤ M ≤ N ≤ 1,000,000)
- 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요
코드
import math
m, n = map(int, input().split())
exp = set()
primes = []
for i in range(2, n+1):
if i in exp:
continue
if i >= m:
primes.append(i)
j = 1
while i * j <= n:
exp.add(i*j)
j+=1
print("\n".join(map(str, primes)))
설명
n = N - M이 최대 백만 정도로, 단순 반복으로 풀기에는 복잡도가 O(n^2)이 되어 시간초과가 날 것입니다. 이를 해결하기위해, 에라토스테네스의 체가 필요합니다.
에라토스테네스의 체는 간단히 말하자면, 소수가 확실히 아닌 수들을 모두 검사 대상에서 제외시키는 것입니다. 말 그대로 소수가 아닌 수들을 체로 걸러내는거죠.
과정을 간략히 살펴보자면, 먼저, 현재 체가 비어있으므로 아무 수도 제외되지 않았습니다. 따라서 2를 추가합니다. 그리고 2의 배수는 모두 제외시킵니다. 다음으로 제외되지않은 수 중 가장 작은 3을 추가합니다. … 이 과정의 반복입니다. 소수는 1과 자기자신만이 약수이므로, 해당 수를 검사하기까지 체에 추가되지 않았다면 자연스럽게 소수가됩니다.
파이썬에서는 set() 객체를 기본적으로 지원하므로, 이를 응용하면 간단합니다. 제외대상인 수를 해당 집합에 모아서 수를 반복하며 제외대상인지 아닌지만 판단합니다. 제외대상이라면 continue가 실행되고, 아니라면 소수여부를 검사할 필요도 없이(그 수까지의 소수가 아닌 수는 모두 걸러졌으므로) 리스트에 추가합니다. 그리고 해당 수의 배수들을 체에 추가합니다.
댓글남기기