백준 4948번 문제(베르트랑 공준) C++로 풀기

4948번 베르트랑 공준 링크

---

문제 요약

입력값 n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

---

코드

#include <iostream>

using namespace std;

const int range=123457; // 문제 범위

int main()
{
  int nums[2*range]={0,};
  for(int j=2;j<2*range;j++)
  {
    nums[j]=j;
  }
  for(int k=2;k<2*range;k++)  // 에라토스테네스의 체
  {
    if(nums[k]==0) continue;
    for(int l=2*k;l<2*range;l+=k)
    {
      nums[l]=0;
    }
  }
  while(1)
  {
    int n;
    scanf("%d",&n);
    if(n==0) break;
    int count =0;
    for(int h=n+1;h<=2*n;h++)
    {
      if(nums[h]!=0)
      {
        count+=1;
      }
    }
    printf("%d\n",count);
  }
}

---

풀이

에라토스테네스 체를 이용한다.

---

주의점

문제 범위가 123,456까지인데, 베르트랑 공준의 정의상 123,456의 두배까지가 실질적으로 필요하다.