Sum of Consecutive Prime Numbers
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 17954 | Accepted: 9863 |
Description
Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For example, the integer 53 has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations 2+3+5+7+11+13, 11+13+17, and 41. The integer 3 has only one representation, which is 3. The integer 20 has no such representations. Note that summands must be consecutive prime
numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.
Your mission is to write a program that reports the number of representations for the given positive integer.
numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20.
Your mission is to write a program that reports the number of representations for the given positive integer.
Input
The input is a sequence of positive integers each in a separate line. The integers are between 2 and 10 000, inclusive. The end of the input is indicated by a zero.
Output
The output should be composed of lines each corresponding to an input line except the last zero. An output line includes the number of representations for the input integer as the sum of one or more consecutive prime numbers. No other characters should be inserted in the output.
Sample Input
2 3 17 41 20 666 12 53 0
Sample Output
1 1 2 3 0 0 1 2
题意:
给出数 N(2 ~ 10000),输出多少种不同的组合数,能由连续素数加和所得。
思路:
素数筛选。离线处理好所有数据,筛选出10000内的素数,另开个数组保存素数,后枚举连续素数即可。
AC:
#include <cstdio> #include <string.h> #define MAX 10005 using namespace std; int n,ans; int pri_num[MAX],time[MAX]; bool pri[MAX]; void make_pri() { for(int i = 0;i < MAX;i++) pri[i] = true; pri[0] = pri[1] = false; for(int i = 2;i * i <= MAX;i++) if(pri[i]) { for(int j = i;j * i <= MAX;j++) pri[i * j] = false; } ans = 0; for(int i = 0;i < MAX;i++) if(pri[i]) pri_num[ans++] = i; memset(time,0,sizeof(time)); for(int i = 2;i < MAX;i++) { for(int j = 0;j < ans;j++) { int sum = 0; if(pri_num[j] > i) break; for(int from = j;from < ans;from++) { sum += pri_num[from]; if(sum > i) break; if(sum == i) { time[i]++; break; } } } } } int main() { make_pri(); while(~scanf("%d",&n) && n) { printf("%d\n",time[n]); } return 0; }
相关推荐
北大POJ2739-Sum of Consecutive Prime Numbers 解题报告+AC代码
连续素数和 一些质数可以表示为其他连续质数的总和。 例如5 = 2 + 3,17 = 2 + 3 + 5 + 7,41 = 2 + 3 + 5 + 7 + 11 + 13。在3到N的范围内,总和应始终以数字2开头。 编写代码以找出在给定范围内满足上述性质的质数...
24.Sum of Consecutive 25.Symmetric Sort 26.The Clock 27.The Ratio of gainers to losers 28.VOL大学乒乓球比赛 29.毕业设计论文打印 30.边沿与内芯的差 31.不会吧,又是A+B 32.不屈的小蜗 33.操场训练 34.插入...
Sum of Consecutive;Arithmetic Progressions;Redistribute wealth;Scoring;Specialized Numbers;操场训练;最长回文子串;寻找规律;公园喷水器;阶乘合计;不屈的小蜗;Hailstone;The Ratio of gainers to ...
A Study of 131 Consecutive Cases of Fibroid Tumors of the Uterus Demanding Operation
The cows in farmer John's herd are ...Write a program that will compute the number of ways farmer John can sum the numbers on consecutive cows to equal N. Do not use precomputation to solve this problem.
可约二次级数连续项的最小公倍数的渐近行为,千国有,洪绍方,设$l$与$m$为满足条件$l>mge 0$的两个整数, 而$f(x)$为一可约的二次整系数 多项式. 在本文中,我们证明$log { m lcm}_{mn<ile ln}{f(i)}=An+o(n)$,...
This puzzle consists of a random sequence of m black disks and n white disks on an oval-shaped track, with a turnstile capable of flipping (i.e., reversing) three consecutive disks. In Figure 1, there...
Consecutive-(r,s,t)-out-of-(m,n,l): F系统的可靠性仿真求解研究,孙鸽,刘胜尧,3 dimensional consecutive-(r,s,t)-out-of-(m,n,l): F系统是一维和二维consecutive-k-out-of-n: F系统的一般化, 当系统中有r×s×t...
Prediction of Consecutive Road Node Congestion Based on Queueing Model
在 x^2 和 x^2+x 之间一定至少存在一个素数,徐万东,,文章中证明了对于奇数的赝序列,在 x^2 和 x^2+x 之间一定至少存在一个赝素数, 那么, 对于真实奇数序列, 在 x^2 和 x^2+x 之间也一定至少存�
Bitwise AND of Numbers Range Power of Three Rectangle Area 数论 Happy Number Ugly Number Ugly Number II Super Ugly Number Fraction to Recurring Decimal Factorial Trailing Zeroes Nim Game 模拟 Reverse ...
+ Range copy selects now the first selected consecutive range of tracks as default + New folder browser dialog (system dialog for folders) + Added two placeholders for filename creation for track ...
We first build a co-prime MIMO configuration using the prototype co-prime array, where the expressions for the range of consecutive lags and the number of unique lags are derived. Then, to fully ...
magic square consisting of consecutive primes. Only Gardner could fit so many diverse and tantalizing problems into one book. <br>This material was drawn from Gardner's column in Issac Asimov's ...
A Quicksum is the sum of the products of each character's position in the packet times the character's value. A space has a value of zero, while letters have a value equal to their position in the ...
Consecutive Sequence 7 Two Sum Hash,夹逼均可 8 3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next Permutation 公式 13 Permutation Sequence 公式 14 Valid ...
A Sublime Text 2 and 3 plugin, that inserts (consecutive) numbers across multiple selections or modifies the selections' contents with expressions. Huge configurability.
f) a straight (i.e., five cards of consecutive face values) g) a full house (i.e., two cards of one face value and three cards of another face value) [Hint: Add methods getFace and getSuit to class ...