1929번 - 소수 구하기

시간제한 : 2초
메모리 제한 : 256MB

---

문제

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

---

입력

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

---

출력

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

---

예제 입력 1

3 16

---

예제 출력 1

3
5
7
11
13

---

시간초과 코드

결과 : 시간초과

import sys

m, n = map(int, sys.stdin.readline().strip().split())

for i in range(m, n+1):
  if i == 1:
    continue
  for j in range(2, i):
    if i % j == 0:
      break
  else:
    print(i)

---

---

에라토스테네스의 체를 이용한 코드

시간 : 5364ms
메모리 : 31256KB

import sys

m, n = map(int, sys.stdin.readline().strip().split())

for i in range(m, n+1):
  if i == 1:
    continue
  for j in range(2, int(i**0.5)+1):
    if i % j == 0:
      break
  else:
    print(i)

---

풀이

이 문제의 경우 시간을 고려하지 않고 단순히 소수를 출력하는 코드를 작성하면 시간초과로 맞힐 수 없다.

그래서 에라토스테네스의 체를 이용해 소수를 구해야한다.

에라토스테네스의 체
마치 체처럼 걸러낸다고 하여 이름 붙인 이 알고리즘은, 2 이상 n 이하의 정수 x가 소수인지 아닌지 효율적으로 판단할 수 있도록 추가적인 배열을 만드는 전처리 알고리즘입니다.

예를 들어 2부터 120까지의 소수를 구한다고 가정했을 때,
11^2 > 120이므로 11보다 작은 소수의 배수들을 지우면 된다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

참고 : 에라토스테네스의 체 - 위키피디아