本文主要是介绍POJ 2739 Sum of Consecutive Prime Numbers 数论,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:给定一个数值,判断他是否等于一连串素数之和(这些素数必须是连续的)。输出满足条件的组合的个数。
题解:预先求出连续的素数和。然后找到不大于n的最大素数,那么所有的组合(连续不断的素数)只可能在此范围内。
#include <cstring>
#include <iostream>
using namespace std;bool flag[10002];
int prime[10002], sum[1402];
int Pnum;int main()
{int i, j, k ;memset(flag,-1,sizeof(flag));memset(sum,0,sizeof(sum));memset(prime,0,sizeof(prime));Pnum = 0;for ( i = 2; i <= 10000; i++ ){if ( flag[i] ){prime[++Pnum] = i;for ( j = 2; i*j <= 10000; j++ )flag[i*j] = 0;}}for ( i = 1; i <= Pnum; i++ )sum[i] = sum[i-1] + prime[i];int n, cnt;while ( cin >> n && n ){cnt = i = 0;while ( prime[i] < n && i < Pnum ) i++; /* 找到不大于n的最大素数 */if ( prime[i] == n ) cnt++; for ( j = i - 1; j >= 1; j-- ){for ( k = 0; k < j; k++ )if ( sum[j] - sum[k] == n )cnt++;}cout << cnt << endl;}return 0;
}
这篇关于POJ 2739 Sum of Consecutive Prime Numbers 数论的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!