#68. 백준 4948번 문제 풀이: 베르트랑 공준 문제 원본 보기
베르트랑은 임의의 자연수 n에 대해 n초과 2n이하의 소수는 최소 하나는 존재한다 했다. 자연수 n이 주어졌을 때, n보다 크고 2n이하인 소소의 개수를 구하라. 입력: 각각의 한 줄이 테스트 케이스이다. 마지막 표시로 0 이 입력된다. 출력: 각 테스트 케이스에 대해, n보다 크고 2n이하인 소수의 개수를 출력하라.
입력/출력
--입력--
1
10
13
100
1000
10000
100000
0
--출력--
1
4
3
21
135
1033
8392
문제풀이+해설
소수는 1과 자신의 수 외에는 나누어지지 않는 1보다 큰 정수를 말한다. 예를 들어, 2, 3, 5, 7 ...
어떤 수가 소수 여부를 판단하려면, 2부터 자신보다 작은 수 까지 %(나머지) 연산을 해서 0으로 떨어지면 나누어지는 수가 있으므로 소수가 아니다.

주어진 범위에 해당하는 자연수를 확인해서 소수를 찾아내어 개수를 카운트해서 출력하면 된다.

여기서 주의할 것은 시간제한이 있다는 것이다. 일반적인 방법으로는 시간초과가 나타난다.
소수개수를 출력하는 케이스가 여러개 주어지기 때문에 그때마다 소수를 계산하는 것은 너무 비효율적이다.
그래서 미리 소수를 계산해 배열에 넣어두고, 요구하는 범위의 소수를 배열에서 가져오는 방식을 사용하면 된다.
code sol.
#include <stdio.h>
#include <math.h> // sqrt 사용을 위해

// 소수 판별 함수 구현
// n: 소수인지 확인할 숫자
// 리턴: 1(소수) 0(소수아님)
int sosu(int n) {
  int i, max_n;
  if(n == 1) return 0; // 1은 소수가 아님
  max_n = (int)sqrt(n); // 제급근까지만 나누어지는 수를 체크하면 됨.
  for(i = 2; i <= max_n; i++) {
    if(n % i == 0) return 0; // 나누어 떨어지면 소수가 아님
  }
  return 1; // 나누어 떨어진 수가 없으면 소수
}

int main() {
  // 소수 갯수를 찾는 케이스가 여러개 주어지므로,
  // 속도를 위해 미리 배열에 소수를 계산해 넣어 둔다.
  // 배열의 인덱스값을 숫자로 간주하고 소수가 아니면 0, 소수이면 1로 설정한다.
  int i, n, n2, count, max = 123456*2;
  int a_sosu[123456*2+1] = {0}; // 소수를 담아둘 배열
  for(i = 2; i <= max; i++) { // 1부터 주어진 최대수 123,456 의 2n까지 계산해 둠.
    a_sosu[i] = sosu(i); // 소수 판별값을 대입 
  }
    
  while(1) { // 무한루프
    scanf("%d", &n); // 값을 하나씩 입력 받아 정수형으로 변환해서 대입
    if(n == 0) break; // 0 값이 들어오면 루프 끝냄
    
    count = 0; // 소수 개수 카운트
    n2 = n*2;
    for(i = n+1; i <= n2 ; i++) { // n ~ n*2까지 루프
      if(a_sosu[i] == 1) count++; // 1(소수) 이면 카운트 증가
    }
    printf("%d\n", count); // 소수 개수 출력
  }
  return 0;
}
© 코드솔 - CodeSol. All Rights Reserved.