[백준] 4948번 베르트랑 공준 (C++) - Prime Number

문제

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

코드

#include <iostream>

using namespace std;

bool check[246913];

int main(){
  for(int i=2; i*i<=246912; i++){
    if(!check[i]){
      for(int j=i*i; j<=246912; j+=i){
        check[j] = true;
      }
    }
  }
  while(true){
    int n;
    cin >> n;
    if(n==0) break;
    int cnt = 0;
    for(int i=n+1; i<=2*n; i++){
      if(!check[i]) cnt++;
    }
    cout << cnt << '\n';
  }
  return 0;
}

정리

에라토스테네스의 체를 이용하여 풀 수 있는 문제이다. 소수를 구할 때는 이 방법이 가장 빠르다.

참조

https://kdongree.tistory.com/77