UVA1210 Sum of Consecutive Prime Numbers题解

本文主要是介绍UVA1210 Sum of Consecutive Prime Numbers题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

有多组数据，每组一个n，以0结尾，若n=0，程序结束，求有多少种方法将n写成连续素数之和（n<=10000）。

分析

可预先将1到10000的素数和其前缀和处理出来，记为数组sum，在进行循环，判断是否有i,j，使得sum[i]-sum[j]=n，若有，则ans++。最后输出ans，时间为80ms。

#include<bits/stdc++.h>
using namespace std;
int prime[10001],sum[10001],v[10001],m=0,n;
void P(){memset(prime,0,sizeof(prime));memset(v,0,sizeof(v));memset(sum,0,sizeof(sum));for(int i=2;i<=10000;i++){if(!v[i]){v[i]=i;prime[++m]=i;sum[m]=sum[m-1]+i;}for(int j=1;j<=m;j++){if(prime[j]>v[i]||prime[j]>10000/i)break;v[i*prime[j]]=prime[j];}}
}
int main(){P();while(scanf("%d",&n)){int ans=0;if(!n)break;for(int i=1;i<=m;i++){for(int j=0;j<i;j++){if(sum[i]-sum[j]==n){ans++;}   }}printf("%d\n",ans);}return 0;
}

这篇关于UVA1210 Sum of Consecutive Prime Numbers题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---