백준 1929번 소수 구하기 - Python

문제는 아래와 같습니다

소수 구하기

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

문제의 요구사항은 m~n까지를 다 훑어보면서 소수를 출력하라는 것 입니다

가장 쉽게 만들 수 있는 코드는 다음과 같습니다

def isPrime(num):
    if num == 1:
        return False
    if num < 4:  # 2,3
        return True

    for i in range(2, num):  # 2 ~ num-1
        if num % i == 0:
            return False
    return True


m, n = map(int, input().split())
for i in range(m,n+1):
    if isPrime(i):
        print(i)

 

하지만 이 문제에서 이렇게 접근하면 시간초과가 발생하는 것을 볼 수 있습니다

시간 초과가 발생한 이유?

(1 ≤ M ≤ N ≤ 1,000,000) 라는 범위를 고려해보면 for i in range(2,num+1)를 순회할때 최대 1000000 번을 순회해야하는 경우가 발생하므로 시간초과가 발생한 것으로 추정됩니다
그렇다면 이 순회 횟수를 줄이는 방법이 무엇이 있을까를 고민해봐야 합니다

이럴 때에 대하여 미리 외워두면 좋은 것이 루트 num 보다 작은 범위 안에서 나누어떨어지는 수가 없다면 이보다 더 큰 수에서 나누어 떨어지는 것은 없다고 보는 것 입니다

그 밖에도 페르마의 소정리, 에라토스테네스의 체를 이용해서 구하는 방법들도 있습니다

import math

def isPrime(num):
    if num == 1:
        return False
    if num < 4:  # 2,3
        return True

    for i in range(2, int(math.sqrt(num)+1)):  # 2 ~ num-1
        if num % i == 0:
            return False
    return True


m, n = map(int, input().split())
for i in range(m,n+1):
    if isPrime(i):
        print(i)

저는 다음과 같이 int(math.sqrt(num)+1)의 범위까지로 순회 길이를 낮춰줌으로써 문제를 해결할 수 있습니다

페르마의 소정리, 에라토스테네스의 체를 이용한 방법도 다른 문제 풀이간에 활용해보겠습니다