[백준] 4948.cpp : 베르트랑 공준

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

#include <iostream>

using namespace std;

int n = 0;
int che[247000] = {1,1};

int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  // 에라토스테네스의 체
  for(int i = 2 ; i < 247000 ; i++)
  {
    if(che[i] == 0)
    {
      for(int j = 2 ; i * j < 247000 ; j++)
      {
        che[i*j] = 1;
      }
    }
  }

  // 너무 쉽다!
  cin >> n;
  while(n)
  {
    int cnt = 0;
    for(int i = n+1 ; i <= 2*n ; i++)
    {
      if(che[i] == 0) cnt++;
    }
    cout << cnt << '\n';

    cin >> n;
  }
}

 

[Try]

1. 이것도 그냥 에라토스테네스의 체 사용하여 풀면 된다. 왜 실버2인지 모르겠을 정도로 단순하다.

 

[Point]

1. 완전탐색으로 n 번 말고 n 의 제곱근 까지만 돌려도 시간내에 돌릴 수 있다.