首页 > 代码库 > UVa 1210 (高效算法设计) Sum of Consecutive Prime Numbers
UVa 1210 (高效算法设计) Sum of Consecutive Prime Numbers
题意：
给出n，求把n写成若干个连续素数之和的方案数。
分析：
这道题非常类似大白书P48的例21，上面详细讲了如何从一个O(n3)的算法优化到O(n2)再到O(nlogn)，最后到O(n)的神一般的优化。
首先筛出10000以内的素数，放到一个数组中，然后求出素数的前缀和B。这样第i个素数一直累加到第j个素数，就可表示为Bj - Bi-1
枚举连续子序列的右端点j，我们要找到Bj - Bi-1 = n，也就是找到Bi-1 = Bj - n。
因为Bj是递增的，所以Bi-1也是递增的，所以我们就不用从头枚举i，而是接着上一次循环i的值继续枚举。
还有就是，因为本身素数也是递增的(废话!)，所以j也不一定要枚举到最后一个素数，只要在不超过n的素数里枚举就行了。
说了这么多，我就是想说人家算法的效率已经很高了，15ms，UVa上居然排300+名，鄙视那些打表狗。
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxn = 10000; 5 const int maxp = 1300; 6 bool vis[maxn + 10]; 7 int prime[maxp], sum[maxp], cnt = 1; 8 9 void Init()10 {11 int m = sqrt(maxn + 0.5);12 for(int i = 2; i <= m; ++i) if(!vis[i])13 for(int j = i * i; j <= maxn; j += i) vis[j] = true;14 for(int i = 2; i <= maxn; ++i) if(!vis[i]) prime[cnt++] = i;15 cnt--;16 //求素数的前缀和17 for(int i = 1; i <= cnt; ++i) sum[i] = sum[i - 1] + prime[i];18 }19 20 int main()21 {22 Init();23 int n;24 while(scanf("%d", &n) == 1 && n)25 {26 int i = 0, ans = 0;27 for(int j = 1;j <= cnt && prime[j] <= n; ++j)28 {29 int temp = sum[j] - n;30 while(sum[i] < temp) ++i;31 if(sum[i] == temp) ans++;32 }33 printf("%d\n", ans);34 }35 36 return 0;37 }
UVa 1210 (高效算法设计) Sum of Consecutive Prime Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。