[백준/1929] 소수 구하기 | 에라토스테네스의 체

개요

백준 소수 문제들이 눈에 들어와서 푸는데,, 이 문제만 같은 방식으로 해결이 안되는 거다.

서칭한 결과 소수 구하기 문제는 시간초과를 주의해야 하고, 

소수 문제에서 시간초과를 피하기 위해 에라토스테네스의 체라는 개념을 알아두면 유용하다는 결론을 내렸다.

(하지만 공부한 결과 모든 소수 문제에 적용되는 것은 아니다..! 끝까지 글을 읽어보자)

 

---

📝 에라토스테네스의 체

에라토스테네스의 체란?

어떤 수 n 이하의 모든 소수를 찾는 간단하고 빠른 방법으로, 자기 자신을 제외한 배수를 모두 차례대로 지우는  방식이다.

더이상 지울 수 없을 때 남아있는 수들이 소수이다.

 

에라토스테네스의 시간복잡도는 O(n log(logn))이다. 

 

에라토스네네스의 체는 '특정 범위 내의 소수'를 판정하는 데에만 효율적이다. 

만약 주어진 수 하나가 소수인가?만을 따진다면, 이는 소수판정법으로 에라토스테네스와는 비교도 안되는 빠른 방법이 넘쳐난다.

 

---

💻 백준 1929 소수구하기(파이썬으로 에라토스테네스의 체 구현)

import sys
m,n = map(int, sys.stdin.readline().split())
prime = [True]*(n+1) # n+1개 만큼의 배열.
prime[0] = False # 0과 1은 소수가 아님.
prime[1] = False

for i in range(2,  int(n**0.5)+1):
    if prime[i]:
        for j in range(i*2, n+1, i):
            prime[j] = False

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

---

 

🤔 사실.... 이렇게만 보고는 잘 이해가 안가서 for문 단계로 print를 찍고 손으로 직접 써서 이해해봤다.

import sys
m,n = map(int, sys.stdin.readline().split())
prime = [True]*(n+1) # n+1개 만큼의 배열.
prime[0] = False # 0과 1은 소수가 아님.
prime[1] = False

for i in range(2,  int(n**0.5)+1):
    #print(i)
    if prime[i]: # prime이 True일 때
        for j in range(i*2, n+1, i):
            #print(j)
            prime[j] = False 

#for i in range(m,n+1):
#    if prime[i]: #prime이 True인 값들에 대해 m부터 n까지 출력
#         print(i)

 

 

 

주석과 필기 내용을 참고해서 직접 써보면 더 이해가 쉽게된다.

이번 기회에 에라토스테네스의 체를 잘 알아두자.