[백준/C++] 1929번 : 소수 구하기(시간 초과, 에라토스테네스의 체)

문제

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

입력

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

출력

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

풀이

이전 문제를 풀었던 방식대로 했으면 시간 초과가 나는 문제이다. 문제 설명에도 나와있듯, 에라토스테네스의 체를 사용해야 한다. 

 

01. 배열을 만들어 0과 1을 제외한 수를 true로 초기화한다.

02. root(max)까지 돌면서 소수의 n배수, 즉 소수가 아닌 값을 false로 표시한다

03. 배열의 크기만큼 for문을 돌면서 소수인 값을 출력한다.

 

문제가 잘 풀리지 않을 경우 아래 팁을 참고하면 쉽다. 개인적으로 도움되었던 것은 5번과 6번이었다.

https://www.acmicpc.net/board/view/39203

05. endl은 버퍼를 flush하기 때문에 매우 느리다. '\n'을 대신 사용하는 것이 좋다
(endl 사용하면 시간 초과가 나는데. \n을 사용하니 바로 해결되었다!)
+ cout 대신 printf를 사용하는 것이 도움이 된다는 글도 있었다. 

06. 에라토스테네스의 체를 구현할 때 흔히 안쪽 루프를 int j = i * i로 시작하는데, 이렇게 하면 i가 46341이 되는 순간부터 i * i가 int의 범위를 초과하기 때문에 오버플로우가 발생합니다. long long을 사용하거나, i * i 대신 i * 2부터 시작하는 등의 방법을 사용하세요.

#include <iostream>
#include <cmath>
using namespace std;

int main(){
  int min, max;
  cin >> min >> max;
  bool isPrime[max+1];
  fill_n(isPrime, max+1, true);

  isPrime[0] = false;
  isPrime[1] = false;

  for (int i=2; i<=sqrt(max); i++){
 	// 소수 가능성이 있는 수들
    if (isPrime[i] == true){
   	// 기존 수의 n배수를 모두 제거한다
      // ex) i = 2이면 2*2, 2*3, 2*4, ...를 false로 표시
      for (int j = i*2; j<=max; j+=i)
        isPrime[j] = false;
    }
  }

  for (int i=min; i<=max; i++){
    if (isPrime[i])
      cout << i << "\n";
  }
}

---

소수 문제가 여러 개 있어서 점점 익숙해진다고 생각했는데 풀 때마다 새로운 개념을 알게 되어서 신기하다!!