AOJ 0009 Prime Number
エラトステネスの篩、生半可な知識で適当に実装してみたら一発で通ったのでらっきー。
bool型の配列って全部初期化すること可能なんでしょうか。
#include <cstdio> #include <iostream> using namespace std; int main(){ int n; while(cin >> n){ bool d[1000000]; int ans = 0; for(int i = 1;i <= n;i++){ d[i] = true; } d[1] = false; for(int i = 1;i <= n;i++){ if(d[i] == true){ ans++; for(int j = 1;j*i <= n;j++){ d[i*j] = false; } } } printf("%d\n",ans); } return 0; }