[Algorithm]エラトステネスの篩

MAX_NUMまでの素数をvector<int> pvecに入れる

 bool isPrime[MAX＿NUM];
 
 int main(void){
   vector<int> pvec;
   //篩
   fill(isPrime,isPrime+MAX_NUM,true);
   for(int i=2;i<=50000;i++){
     if(isPrime[i] == true){
       pvec.push_back(i);
       for(int j=2;i*j<MAX_NUM;j++){
         isPrime[i*j] = false;
       }
     }
   }
 }

MAX_N番目の素数までを列挙してpに入れる(MAX_NUMはMAX_N番目の素数より大きくなるように設定する)

 int p[MAX_N];
 bool isPrime[MAX_NUM];
 
 int main(void){
   int pnum=0;
   //篩
   fill(isPrime,isPrime+MAX_NUM,true);
   for(int i=2;pnum<MAX_N;i++){
      if(isPrime[i] == true){
       p[pnum++] = i;
       for(int j=2;i*j<MAX_NUM;j++){
         isPrime[i*j] = false;
       }
     }
   }
 }