AOJ Volume0 0009: Prime Number

素数テーブルの作成にはエラトステネスの篩を用いる。

/********************************
*    2012/03/21                
*    AOJ Volume0 0009          
*    Prime Number              
*    crane                     
*********************************/

#include<cmath>
#include<iostream>
using namespace std;
#define MAX_N 1000000

void prime();

bool field[MAX_N];

int main(){
 prime();

 int input=0;
 while(cin >> input){ //6桁以下の正の整数
  int result = 0;
  for(int i=0; i<=input; i++)
   if(field[i]) result++;
  cout << result << endl;
 }
 return 0;
}


/*******エラトステネスのふるい********/
void prime(){

 field[0] = false;  field[1] = false;
 for(int i=2; i<MAX_N; i++) field[i] = true;

 for(int i=2; i<sqrt((double)MAX_N)+1; i++)
  if(field[i])
   for(int j=i*2; j<MAX_N; j+=i)
    field[j] = false;
}