AOJ Volume0-0009

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp

参考:エラトステネスの篩
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
using namespace std;

list<int> Sieve_of_Eratosthenes(int MAX) {
    list<int> nl,pl;
    list<int>::iterator it;
    
    //自然数の作成 STEP1
    for (int i=5; i < MAX; i+=2) {
        if (i % 3 != 0) {
            nl.push_back(i);
        }
    }
    pl.push_back(2);
    pl.push_back(3);
    
    while (1) {
        //STEP2
        pl.push_back(nl.front());
        
        
        //STEP3
        for(it=nl.begin(); it!=nl.end(); it++) {
            if (*it % pl.back() == 0) {
                *it = 0;
            }
        }
        nl.remove(0);
        
        //STEP4
        if (pl.back() * pl.back() > nl.back()) {
            break;
        }
        
    }
    
    //後処理 listの結合
    pl.merge(nl);
    
    return pl;
}

int main ()
{
    list<int>::iterator it;
    list<int> pl = Sieve_of_Eratosthenes(10000);
    
    
    int n = 0;
    while (cin >> n) {
        int count = 0;
        for (it = pl.begin(); it != pl.end() ;it++) {
            if (*it <= n) {
                count++;
            }else {
                break;
            }
        }
        cout << count << endl;
    }
    
    return 0;
}