백준 [1929번]

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

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

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

• 예제 입력 1
  3 16

• 예제 출력 1
  3
  5
  7
  11
  13

• 처음 제출한 코드

m, n = map(int, input().split())
if m <= 2 <= n:
    print(2)
for i in range(m, n+1):
    for j in range(2, i):
        if i % j == 0: break
        if j == i-1: print(i)

시간 초과로 제출이 거부되었다. 시간을 줄이는 방법으로 무엇이 있을까?

• 기존 코드의 시간 복잡도는 O(n)이다. 하지만 "에라토스테네스의 체"를 이용하여 O(n½)로 줄일 수 있다.

만약 2와 25가 입력으로 주어졌다면, 2, 3, 5의 배수만 체크하여 제거하면 되고, 7의 배수는 7의 제곱이 49가 되어 2 ~ 25 범위를 넘어가므로 굳이 체크할 필요가 없게 된다.

• 수정하여 제출한 코드

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

def isprime(m, n):
  n += 1                            # for문 사용을 위한 n += 1
  prime = [True] * n                # n개의 [True]가 있는 리스트 생성
  for i in range(2, int(n**0.5)+1): # n의 제곱근까지만 검사
    if prime[i]:                    # prime[i]가 True일때
      for j in range(2*i, n, i):    # prime 내 i의 배수들을 False로 변환
        prime[j] = False

  for i in range(m, n):
    if i > 1 and prime[i] == True:  # 1 이상이면서 남은 소수들을 출력
      print(i)

isprime(m, n)

모든 원소가 True인 배열을 만들고, 소수의 배수에 해당하는 인덱스에 False를 넣음으로써 True인 원소만 출력하는 방식이다.