AOJ0009PrimeNumber

2017/12/05

エラトステネスの篩、生半可な知識で適当に実装してみたら一発で通ったのでらっきー。

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
",ans);
  }
  
  return 0;
  
}