| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 19895 | Accepted: 10906 |
Description
Input
Output
Sample Input
2 3 17 41 20 666 12 53 0
Sample Output
1 1 2 3 0 0 1 2
题目分析:给你一个数，如果这个数能够表示成几个连续的素数相加的形式，请问有多少种这样的形式。
例如：41=2+3+5+7+11+13
41=11+13+17
41=41 共有3种
像这种7+13=20 或者 3+5+5+7=20 这些都是不合法的。
算法分析：数据范围不大，先将1000以内的素数存在一个数组里，两层循环进行暴力枚举
外层循环控制最小的素数累加和的起点数，从它开始一直累加下去直到>=输入数。
如果累加和==n，计数器++，最后输出结果。
代码如下：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int prime[2000], total=0;
bool isprime(int k )
{
for(int i=0; i<total; i++)
{
if(k%prime[i] == 0)
{
return false;
}
}
return true;
}
int main()
{
int i, j;
for( i=2; i<=10000; i++)
{
if(isprime(i))
{
prime[total++]=i;
}
}
prime[total]=10001; //???
int n;
while(scanf("%d", &n)!=EOF)
{
if(n==0)
break;
int ans=0;
for(i=0; n>=prime[i]; i++)
{
int cnt=0;
for(j=i; j<total &&cnt<n; j++)
{
cnt+=prime[j];
}
if(cnt==n)
{
++ans;
}
}
printf("%d\n", ans );
}
return 0;
}
POJ 2739 Sum of Consecutive Prime Numbers( *【素数存表】+暴力枚举 )
原文：http://www.cnblogs.com/yspworld/p/4242050.html