poj3292-类素数筛选法

#include<iostream>
using namespace std;
const int N=1000002;
int array[N]={0};
int main(){
int n;
for(int i=5;i<=N;i+=4){
  for(int j=5;j<=N;j+=4){
   int num=i*j;
   if(i*j>N)
   break;
   if(array[i]==0&&array[j]==0)
   //如果 i,j 目前都不为两个数的乘积，那么i*j就是由两个类素数相乘的积；如果之后 i,j 不是类素数，那么由下面的语句也会将其替换成-1.
   array[num]=1;
   else
   array[num]=-1;
  }
}
int count=0;
for(int i=0;i<N;i++){
  if(array[i]==1)
  count++;//设置累加器，输出所求数的个数
  array[i]=count;
}
while(cin>>n,n!=0){
  cout<<n<<" "<<array[n+1]<<endl;
}
return 0;
}

巴特西

poj3292-类素数筛选法

最新文章

热门文章