[백준] 1929번 : 소수 구하기 (python 파이썬) [에라토스테네스의 체]

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

1929번: 소수 구하기

 

 

---

문제 설명

문제 정리 : M이상 N이하의 소수를 증가하는 순서대로 출력

import sys
import math
m,n = map(int,input().split(" "))

l = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화

for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지
    if l[i] == True: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i * j <= n:
            l[i * j] = False
            j += 1

# 모든 소수 출력
for i in range(m, n + 1):
    if l[i]:
        if i != 1:
            print(i)

 

 

 

 

 

 

 

---

문제 해설

 

 

 

에라토스테네스의 체 알고리즘을 통해 해결할 수 있다.

ex) 1~100 까지 자연수중 소수 찾기

1) 1~100까지 쓰기

2) 1 제거 (1은 소수가 아님)

3) 2를 제외한 2의 배수 제거

4) 3을 제외한 3의 배수 제거

5) 5를 제외한 5의 배수 제거

6) 7을 제외한 7의 배수 제거

4와 6은 2)단계에서 제거 됐으므로 고려할 필요 없다

 

100보다 작은 m에 대해서 m = a*b 라면, a와 b 중 적어도 하나는 100의 제곱근인 10보다 같거나 작아야한다. 

따라서 100보다 작은 소수를 찾을 때, 제곱근인 10보다 작은 수의 배수만 검사해도 전수조사가 가능하다.