C++素数筛选法

#include<bits/stdc++.h> using namespace std; const int arrSize=1001; int prime[arrSize]; //保存素数 int primeSize; //限定范围内素数个数 bool mark[arrSize]; //用来做标记 void primeFilter(){ primeSize=0; for(int i=2;i<arrSize;i++){ if(!mark[i]){ prime[primeSize++]=i; for(int j=i*i;j<arrSize;j+=i) mark[j]=true; //从i*i开始 } } /*另一种写法*/ /*for(int i=2;i<arrSize;i++){ if(mark[i]) continue; prime[primeSize++]=i; if(i>1000) continue; for(int j=i*i;j<arrSize;j+=i) mark[j]=true; }//*/ } long long numPrime[1001]; int valPrime[1000]; int valSize[1000]; int main(){ long long num; long long val,temp1,temp2; primeFilter(); while(scanf("%lld",&num)!=EOF){ scanf("%lld",&val); for(int i=0;i<1001;i++){ numPrime[i]=0; valPrime[i]=0; valSize[i]=0; } for(int i=2;i<=num;i++){ if(!mark[i]) numPrime[i]++; else{ temp2=i; for(int j=0;j<primeSize;j++){ while(temp2%prime[j]==0){ numPrime[prime[j]]++; temp2/=prime[j]; } if(temp2==1) break; } } } long long index=0; for(int i=0;i<primeSize;i++){ if(val%prime[i]==0) { while(val%prime[i]==0){ valSize[index]++;//保存每个分解出的素数的个数 val/=prime[i]; } valPrime[index++]=prime[i];//将分解出的素数值保存下来 if(val==1) break; } } int min=10000; for(int i=0;i<index;i++){ temp1=numPrime[valPrime[i]]/valSize[i]; if(temp1<min) min=temp1; } printf("%d\n",min); } return 0; }