문제 링크

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

문제 설명

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

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

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

문제 풀이

아래와 같이 단순한 반복문으로 소수 구하기를 실행한다면, n-m 이 백만일 때 O(n^2)로 시간초과가 날 것이다.

def isPrime(n):
  for i in range(2, n):
    if n % 2 == 0:
      print("소수가 아닙니다")
      return
      
  print("소수 입니다")
    

이럴때는 에라토스테네스의 체를 이용하여 빠르게 소수를 구할 수 있다.

에라토스테네스의 체

임의의 자연수 n이 있으면 그 이하의 소수들을 전부 찾아내는 데 있어서 최적화된 알고리즘이라고 할 수 있다.

• i=2 부터 시작하여 i가 소수가 아니라면, i를 제외한 i의 배수들은 전부 소수가 아니다.
• 배수를 체크하므로, i는 n의 제곱근까지만 검사하면 된다.
• 체크되지 않은 수들이 소수다.

맞은 코드

import math

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

isPrime = [1 for _ in range(n+1)]
isPrime[0], isPrime[1] = 0, 0

length = int(math.sqrt(n))

for i in range(2, length+1):
  if isPrime[i]:
    for j in range(i*2, n+1, i):
      isPrime[j] = 0

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