문제 링크

이 문제는 다른 소수 구하기 문제들처럼 풀었다가는 시간 초과가 되었다. 시간 초과가 됐던 처음 풀이는 다음과 같았다. 다음과 같이 풀이하면 1~N-1 까지 모두 나눠보기 때문에 소수를 판단하려면 O(N)의 시간 복잡도를 갖게 된다.

import sys
input = sys.stdin.readline

m, n = map(int, input().split())

for i in range(m, n+1):
  flag = False
  for j in range(1, i):
    if(j != 1 and i % j == 0):
      flag = True
      break
  if not flag:
    print(i)

더 빨리 풀이하는 방법을 살펴봤다.

1. 제곱근 N의 약수가 무조건 N의 제곱근 번위에 존재한다는 특성을 이용하는 것이다. N의 제곱근까지만 나누어 떨어지는지 여부를 조사하면 더 빠른 소수 판별이 가능하다.

2. 에라토스테네스의 체 소수 N의 배수는 약수로 소수 N을 포함하기 때문에 절대 소수의 배수는 소수가 될 수 없다. 이를 이용해서 소수를 골라내는 방법이 에라토스테네스의 체이다.

제곱근 활용 풀이

import sys

input = sys.stdin.readline

m, n = map(int, input().split())

def isPrime(x):
  if(x<2):
    return False
  for i in range(2, int(x**0.5) + 1):
    if(x%i==0):
      return False
  return True

for i in range(m, n+1):
  if isPrime(i):
    print(i)

에라토스테네스의 체 활용 풀이

위키백과의 코드를 데려와 수정해서 풀이했다. 최소 범위에 대한 지정을 해주지 않았는데도, 앞선 제곱근만 활용해서 단축시킨 시간보다 훨씬 빨랐다. 최소 범위도 지정해주면 더 빠르겠다.

시간 복잡도는 O(nloglogn)이다.

import sys

input = sys.stdin.readline

m, n = map(int, input().split())

def prime_list(a):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * a

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(a ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, a, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, a) if sieve[i] == True]


for num in prime_list(n+1):
  if num >= m:
    print(num)