백준) 1929 - 소수 구하기

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

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

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

m, n = map(int, input().split())
isPrime = [True]*(n+1)
for i in range(2, int(n**0.5)+1):
  if isPrime[i]:
    for j in range(i+i, n+1, i):
      isPrime[j] = False
for de in [i for i in range(2, n+1) if isPrime[i] == True]:
  if de >= m:
    print(de)

풀이 : 원래 쓰던 방식인 n이라는 어떤 숫자에 대해서 1부터 시작하여 n까지의 수로 나누어보며 나머지가 0인 경우를 이용하는 식으로는 시간초과가 뜨며 문제를 해결할 수 없었다. 그래서 이번 문제에서는 문제 설명란에 있었던 '에라토스테네스의 체'를 이용하여 문제를 해결하였다. 자세한 설명은 해당 링크 참조.

m, n(m≤n)을 입력받으면 (n+1)개의 리스트를 만들고 내용은 True로 채워준다. 그 뒤 에라토스테네스의 체를 이용하여 차례대로 소수들의 배수에 해당하는 인덱스의 내용을 False로 교체해준다. 그 뒤에는 m보다 크고 n보다 작은 범위 내의 소수들을 출력해준다.