(4948) 베르트랑 공준

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

단계별로 풀어보기

15단계(약수, 배수와 소수 2) 7번째

 

 

 

#include <iostream>
using namespace std;
#define p 246913 // 1+123456*2

int main() 
{
  bool soe[p]= {true, true, false, };
  
  for(int i=4;i<=p;i+=2)  soe[i]= true;
  for(int i=3;i*i<=p;i+=2){
    if(soe[i])  continue;
    
    for(int j=i;i*j<=p;j+=2)  soe[i*j]= true;
  }
  
  while(true){
    int n, res= 0;
    
    cin >> n;
    
    if(!n)  break;
    
    for(int i=n+1;i<=2*n;i++)  res+= (!soe[i]);
    
    cout << res << "\n";
  }
  
  return 0;
}