統計素数個数

再開
acm.hnust.edu.cn
問題C:実験3-3:統計素数個数
時間制限:2 Sec
メモリ制限:128 MB
コミット:2068
解決:1048
[コミット][ステータス][ディスカッション]
タイトルの説明
 
キーボードから整数n(98000<=n<=10000000)を入力し、1からnの範囲の素数の個数を統計します.
素数とも呼ばれる.1より大きい自然数のうち、1とこの整数自体を除いて、他の自然数では割り切れない数を指す.言い換えれば、2つの正因数(1と自分)の自然数だけが素数である.1より大きいが素数ではない数を合数と呼ぶ.1と0は素数でも合数でもない.
入力
整数n(98000<=n<=10000000)を入力します.
しゅつりょく
素数の個数
サンプル入力
100000
サンプル出力
9592

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
const int maxn=1<<30;
const int SIZE=1e5+10;
const double pi=acos(-1);
using namespace std;
int prim[SIZE];
void get_prim(){
    memset(prim,0,sizeof(prim));
    for(LL i=2;i<SIZE;i++){
        if(!prim[i]){
            prim[++prim[0]]=i;
            for(LL j=i*i;j<SIZE;j+=i)
                prim[j]=1;
        }
    }
}
int main()
{
    get_prim();
    int n;
    scanf("%d",&n);
    int pos=lower_bound(prim+1,prim+prim[0],n)-prim;
    if(prim[pos]==n)printf("%d
",pos);
    else printf("%d
",pos-1);
    return 0;
}