首页 > 代码库 > sicily 1259. Sum of Consecutive Primes
sicily 1259. Sum of Consecutive Primes
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. 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  Copy sample input to clipboard 2317412066612530 Sample Output 11230012
|
分析：首先根据题目要求是给定一个数，找到能够满足如下条件的序列个数： 序列所有元素是连续的素数 序列元素之和为给定数首先我们已知数值范围是 2~10000，那么先找到 2~10000里面的所有素数，而不应该在每输入一个数都重新找一次。还有一个是素数是要连续的，这样在寻找的时候就减少了很多搜索。对于每一个数都只需要判断它的下一个。算法思想如下： 从小于给定数的最大素数出发，利用深搜，剪枝依据是每个元素的子节点只能是其素数列表的前一个元素，比如给定 10，那么第一个素数为7 7 5 > 10 5 3 2 == 10 3 2 终止 2 终止在深搜的时候，判断当前素数之和是不是小于给定数，如果不是，就不需要继续考虑其子节点了。
#include <iostream>#include <stack>#include <cstring>#include <map>using namespace std;void getPrimerList(map<int, int> &primerList, int num) { // 找到给定范围的所有素数 int *array = new int[num]; memset(array, 0, sizeof(array) * num); int k = 0; for (int i = 2; i < num; ++i) { if (array[i] == 0) { primerList[k++] = i; for (int j = 2 * i; j < num; j += i) { array[j] = 1; } } }}struct Node { Node(int v = 0, int s = 0): value(v), sum(s) { } int value; int sum;};int main(int argc, char const *argv[]){ map<int, int> primerList; getPrimerList(primerList, 10000); int number; while (cin >> number && number != 0) { int factorListNum = 0; if (number >= 2) { int numT; map<int, int>::iterator iter = primerList.end(); --iter; for (; iter != primerList.begin(); --iter) { if (iter->second <= number) { numT = iter->second; break; } } if (iter == primerList.begin()) numT = iter->second; stack<Node> s; // 从小于等于给定数的第一个素数开始，以每个素数为起点向前查找 // 也就是说，这里相当于深搜多棵树 for (; iter != primerList.begin(); --iter) { s.push(Node(iter->first, iter->second)); } s.push(Node(iter->first, iter->second)); while (!s.empty()) { Node curent = s.top(); s.pop(); if (curent.sum == number) { factorListNum++; } else if (curent.sum < number){ if ((curent.value - 1) >= 0) { s.push(Node(curent.value - 1, primerList[curent.value - 1] + curent.sum)); } } // else 其他情况下就不再需要继续往下子节点遍历 } } cout << factorListNum << endl; } return 0;}
sicily 1259. Sum of Consecutive Primes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。