[백준 Python] - 1929 소수 구하기 '에라토스테네스의 체'

1. 문제 - 1929번

2. 접근법

처음에 이전의 소수 구하기 문제처럼 생각하고 풀었다가, 몇번이고 시간 초과가 나왔다.

찾아보니 최대 공약수에 유클리드 호제법이 있는 것처럼, 소수 문제의 경우 에라토스테네스의 체라 불리는 일종의 노가다식 풀이법이 있다는 것을 알게 되었다. 노가다이지만, 가장 빠른 알고리즘이라는 것도.

왜 노가다인가 하면, 특정 조건( 2부터 √n 까지 의 수 중 하나라도 약수로 가진 수)을 걸어  소수에 해당하지 않는 수를 뭉텅이로 지워나가는 논리이기 때문이다.

내가 에라토스테네스의 체의 논리를 이해한 바는 이렇다.

    - 현재까지 검증된 방법 중, 소수를 찾는 가장 빠른 방법
    - 특정 범위(ex. 1~n)까지의 소수를 알고 싶다면, n까지의 모든 수의 배수가 아니라  √n 까지만 나누어 보면 됨
    - 만약 n보다 작은 어떤 수 m이 a와 b로 이루어진 합성수 ab라면 a와 b 중 적어도 하나는 √n 이하이기 때문

    - 귀류법으로 증명 : 
      만약 a와 b가 모두 √n 보다 크거나 같다면, 두 수의 곱 m은 n보다 반드시 크거나 같아야 하므로 m이 n보다 작다는 전제에 모순된다.
      따라서 a 또는 b 중 하나 이상은 반드시 √n  보다 작다는 것을 알 수 있다.
  
    - 코드 구현을 위한 해석 :
      이를 코드로 해석하면, n - 1 이하의 모든 수에 대하여, √n 보다 작은 수에 대해서만 약수 여부를 검사하면 m이 소수가 아닌 합성수일 경우, m를 구성하는 a 또는 b는 √n 보다 작은 수로 나누어 떨어지므로 제거할 수 있음
      n - 1 이하의 모든 임의의 수 m에 대해 이런 규칙이 적용되므로 특정 범위 내의 소수가 아닌 모든 수를 지울 수 있게 됨

 <정답 코드>

from sys import stdin

input = stdin.readline

def asdf(m,n):
    for i in range(m, n+1):
        prime  = True
        for j in range(2, int(i**0.5)+1):
            if i%j == 0:
                prime = False
                break
        if prime and i != 1:
            print(i)
    
m, n = map(int, input().split())

asdf(m,n)

백준에서 시간 초과가 나온다는 건 시간 복잡도가 문제에서 원하는 것보다 크다는 것이고, 이는 곧 코드가 잘못되었다는 것.

위에서 이해한 논리대로 코드를 구현해 제출했음에도 다시 시간 초과가 나왔다.
원인을 분석하고 코드를 다음과 같이 다시 고친 결과 통과할 수 있었다.

첫째, 소수가 아닌 1을 제거해주는 코드를 추가.
둘째, m에서 n 사이의 임의의 수 i를 j로 나눴을 때 한번이라도 약수라는 것이 판명되어 prime의 bool 값이 False가 되면 다른 수에 대한 불필요한 반복문 실행이 없도록 내부 반목문을  break로 종료.