解题思路:
旨在构造一个素数数组,利用素数判断一个数是不是素数, 如果是,则补充到素数数组中,以此类推就可以快速地找到 n以内所有素数。
注意事项:
参考代码:
#include<iostream> using namespace std; const int M=100001; unsigned long long a[M]={0}; int main() { int n; while(cin>>n) { a[0]=2,a[1]=3,a[2]=5,a[3]=7; int t=4; for(int i=11;;i+=2) { if(n<4||t==n) break; int ok=1; for(int j=1;a[j]*a[j]<=i;j++) //这里没必要考虑素数数组中所有的数,a[j]<=sqrt(i)即可 { if(i%a[j]==0) { ok=0; break; } } if(ok) a[t++]=i; } unsigned long long sum=1; for(int i=0;i<n;i++) { sum*=a[i]; sum%=50000; } cout<<sum<<endl; } return 0; }
0.0分
0 人评分