백준 1929 번 문제 풀이 C++ :소수 구하기

#67. 백준 1929번 문제 풀이: 소수 구하기

M이상 N이하의 소수를 모두 출력하시오. 입력: 자연수 M N. (1 ≤ M ≤ N ≤ 1,000,000) 출력: 한 줄에 하나씩, 작은 소수 부터 출력

입력/출력

--입력--
3 16
--출력--
3
5
7
11
13

문제풀이+해설

소수는 1과 자신의 수 외에는 나누어지지 않는 1보다 큰 정수를 말한다. 예를 들어, 2, 3, 5, 7 ...

일반적으로 정수를 증가시키면서 나누어 떨어지는지 여부로 검사를 하면 답은 쉽게 찾을 수 있지만,
알고리즘 체크를 하면 "시간초과"가 나온다. 즉, 일반적인 풀이법으로 풀지 말라는 의도이다.

대부분 처음 들었을 에라토스테네스의 체 라는 알고리즘을 사용해야 문제를 풀 수 있다.
알고리즘의 원리는 다음과 같다.

소수가 1과 자신의 수외에는 나누어 떨어지는 수가 없어야 하므로.
특정수의 배수는 소수가 아니다.
즉, 자신을 제외한 배수, 2의 배수(4,6,..) 3의 배수(6,9,..) 4의 배수(2의 배수이므로 생략) 5의 배수(10,15,..) 등은 소수가 아니다.
우리가 머리로 계산하는 건 불가능한 방법이지만, 프로그램으로는 배열을 사용하면 되기때문에 좋은 방법이다.

예를 들어 10까지의 소수를 찾는다면.
배열 S[11]을 0으로 초기화. 소수인 경우를 0, 소수가 아니면 1값을 넣도록 하겠다. 
ⓞ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ : 인덱스(위치)
[0,0,0,0,0,0,0,0,0,0,0] : 인덱스값을 숫자라 가정하자.
[1,1,0,0,0,0,0,0,0,0,0] : 0,1은 소수가 아니므로 1값 
[1,1,0,0,1,0,1,0,1,0,1] : 2의 배수 (4,6,8,10) 배열도 1값
[1,1,0,0,1,0,1,0,1,1,1] : 3의 배수 (6,9) 배열도 1값 
4의 배수(8:2의배수에서 처리됨)
5의 배수(10:2의배수에서 처리됨)
6 이상은 10까지 배수가 없으므로 끝.

결론적으로 0값을 가진 인덱스값은 2,3,5,7 이 된다. 즉 소수이다.

규칙을 보면 한가지 더 고려해도 될 사항이 있다. 최대값의 제곱근(10의 제곱근=3.16..) 이상은 이미 그 이전에 체크된다는 것이다. 그러므로 체크할 개수를 줄일 수 있다.

모든 숫자를 연산하는 것보다 훨씬 빠르고, 연산횟수가 훨씬 적어지기 때문에, 위의 원리를 그대로 코드로 구현하면 된다.

추가적으로 주의할 것은 시간제한이 있기 때문에, C++의 경우 입출력 부분도 속도를 빠른 방법으로 처리해야 한다.
C++ 풀이를 선택하면 그에 대한 방법이 설명되어 있다.C++ 에서 cin, cout 을 사용할 경우, 속도가 더 빨라야 한다면 다음과 같이 선언한다.
  ios_base::sync_with_stdio(false);
  cout.tie(NULL); cout.tie(NULL); 
이것은 표준 C언어 입출력함수들(scanf,printf 등)과 서로 동기화를 끊어줌으로서 속도를 빠르게 해 준다.

또한 cout << endl; 처럼 endl 을 쓸 경우 버퍼를 비우는 과정이 들어가기 때문에 속도를 느리게 하는 요인이 있다.
대신에 개행문자(\n)를 직접 써 주면 속도가 개선된다.

code sol.

코드편집/실행

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

int main() {
  ios_base::sync_with_stdio(false);
  cout.tie(NULL); cout.tie(NULL); 
  // 입출력 속도를 빠르게 하기 위해 설정 기본C 입출력과 동기화를 끊음.

  int i, j, M, N, max_n;
  int S[1000001] = {0}; // 소수정보를 저장할 배열, 0으로 초기화.
  // 인덱스값을 숫자로 가정하고, 값 0(소수) 1(소수아님)으로 가정
  cin >> M >> N; // 숫자 M, N 을 입력받아 정수형으로 대입
  S[0] = 1; S[1] = 1; // 0, 1은 소수가 아닌값(1)으로 설정
  max_n = (int)sqrt(N); // 최대값의 제곱근까지의 숫자만 배수를 체크하면 됨.
  for(i = 2; i <= max_n; i++) { // 2,3,은 소수이므로 2*2=4부터 계산하도록 i=2 부터 
    if(S[i] == 1) continue; // i가 소수가 아닌 상태면, 이미 체크한 배수이므로 건너뜀
    for(j = 2; i * j <= N; j++) {
      S[i * j] = 1; // 배수들은 소수가 아님. 1로 설정
    }
  }
  // 모든 소수 작은 수부터 출력
  for(i = M; i<=N; i++) {
    if(S[i] == 0) cout << i << '\n'; 
    // 소수이면 소수 출력. 속도를 위해 endl 대신 \n 사용
  }
  return 0;
}