题意:给你一个数问你用连续的素数来表示这个数有几种表示方法。
先打一个素数表,再把素数表变下形,prime[i]存prime[i]之前的素数和,循环一下打出ans表即可。
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 10050 int prime[maxn],nprime,ans[maxn]; bool isprime[maxn]; void getprime() { memset(isprime,1,sizeof(isprime)); nprime=0; long long i,j; for(i=2; i<maxn; i++) if(isprime[i]) { prime[++nprime]=i; for(j=i*i; j<maxn; j+=i) isprime[j]=0; } } int main() { getprime(); prime[0]=0; memset(ans,0,sizeof(ans)); for(int i=2; i<=nprime; i++) prime[i]=prime[i]+prime[i-1]; for(int i=0; i<=nprime; i++) for(int j=i+1; j<=nprime; j++) if(prime[j]-prime[i]<maxn) ans[prime[j]-prime[i]]++; else break; int n; while(~scanf("%d",&n),n) printf("%d\n",ans[n]); return 0; }
时间: 2024-12-01 09:20:42