エラトステネスのふるいで素数判定
Posted: 2013年2月21日(木) 13:01
入力されたn(最大6桁)まで何個素数があるか判定します。ただしデータセットは30までとします。
int型なら6桁など余裕だと思ったのですが中々うまくいきません。また思い切ってlong long int にしてもうまくいきませんでした。何故でしょうか？？
よろしくお願いしますm(__)m
int型なら6桁など余裕だと思ったのですが中々うまくいきません。また思い切ってlong long int にしてもうまくいきませんでした。何故でしょうか？？
#include <iostream>
using namespace std;
int main(){
int n,set=0;
while(cin>>n){
set++;
if(set==30) break;
int *array=new int[n];
int count=0;
for(int i=2; i<=n; i++){
array[i]=1; //1で初期化しすべての数を仮に素数としておく
}
for(int i=2; i<=n; i++){
//iを素数だと決定するとiの倍数は素数でないので0にしておく
if(array[i]==1)
for(int j=i; i*j<=n; j++) array[i*j]=0;
}
for(int i=2; i<=n; i++)
if(array[i]==1){
++count;
}
cout<<count<<endl;
}
return 0;
}