题意:
求连续素数和。
思路:
先扫一遍10000的数字,找出素数大概1200+个。
然后对1000+个素数前n项求和。
然后对o(1000*1000)的算法:
遍历i j
i代表连续素数的开头位置,j代表末尾。
这样每次扫出的和的hash值++即可。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #include<queue> #include<cmath> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define Abs(a) ((a)>0?(a):(-(a))) #define llong long long int using namespace std; const int N=10000; const int inf=(1<<30); int n,m; int cnt[N+10]; int prime[N]; int sum[N]; int ans[N+10]; void init() { n=0; for(int i=2;i<=N;i++) { bool flag=true; for(int j=2;j<=sqrt((double)i);j++) { if(i%j==0) { flag=false; } } if(flag) prime[++n]=i; } } void solve() { memset(ans,0,sizeof(ans)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+prime[i]; } for(int i=1;i<=n;i++) for(int j=0;j<=i-1;j++) { int tmp=sum[i]-sum[j]; if(tmp<=N) ans[tmp]++; } } int main() { init(); solve(); int num; while(scanf("%d",&num),num) { printf("%d\n",ans[num]); } return 0; }