문제

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

입력

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

출력

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

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

풀이 - 오답 (Python)

import sys
from collections import deque
input = sys.stdin.readline

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

numbers = list(i for i in range(2, n))
prime_numbers = deque()

for i in range(2, len(numbers)+1):
    for j in range(2, i):
        if i % j == 0:
            break
    else:
        prime_numbers.append(i)

for i in prime_numbers:
    if m <= i <= n:
        print(i)

굉장히 일반적인 풀이로 했을 때 시간초과가 발생했다.

소요 시간을 줄여보고자 append 시간복잡도가 O(1)인 deque 자료구조를 사용해봤는데도 시간초과가 발생했다.

풀이 - 정답 (Java)

public class Main {

  // 입력값의 최대 범위인 1000000 까지의 배열을 static으로 선언
  // 인덱스에 해당하는 수가 실제 정수를 가리킨다 : prime[0] == 0, prime[1] == 1 ...
  // 소수에 해당하는 숫자는 False를 가진다
  public static boolean[] prime = new boolean[1000000];

  public static void Eratosthenes(int start, int end) {

      // 정수 0과 1은 소수가 아니므로 true 를 할당한다.
      prime[0] = prime[1] = true;

      // 정수 2부터 순회한다. (해당 숫자의 제곱에 해당하는 수 까지만 순회를 하면된다.)
      for (int i = 2; i * i <= end; i++) {

          // 현재 순회하고 있는 정수가 false 즉, 소수면
          if (!prime[i]) {

              // 해당하는 정수의 제곱 수 부터 문제에서 요구하는 숫자의 범위까지 순회하여
              // 소수가 아님을 나타내준다.
              for (int j = i * i; j <= end; j += i){
                  prime[j] = true;
              }
          }
      }
  }

  public static void main(String[] args) {

      Scanner sc = new Scanner(System.in);

      int start = Integer.parseInt((sc.next()));
      int end = Integer.parseInt(sc.next());

      Eratosthenes(start, end);

      // 소수 출력
      for (int i = 1; i <= end; i++) {
          if (!prime[i] && i >= start) {
              System.out.println(i);
          }
      }
  }

}

에라토스테네스의 체를 구현한 코드는 시간초과가 발생하지 않았다.

에라토스테네스의 체란?

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

소수가 되는 수의 배수를 지우면 남은 건은 소수만 된다

자기 자신을 제외한 2의 배수를 모두 지운다.

남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.

자기 자신을 제외한 3의 배수를 모두 지운다.

남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.

자기 자신을 제외한 5의 배수를 모두 지운다.

위 과정을 반복한다.

728x90

저작자표시