It is possible to write ten as the sum of primes in exactly five different ways:
7 + 35 + 55 + 3 + 23 + 3 + 2 + 22 + 2 + 2 + 2 + 2
What is the first value which can be written as the sum of primes in over five thousand different ways?
#include <iostream>#include <string>using namespace std;int prime[1000]; //存储前1000个质数bool vis[10000];void getPrime(){int count = 0;memset(vis, 0, sizeof(vis));for (int i = 2; i < 10000; i++){if (!vis[i]){if (count >= 1000)break;prime[count++] = i;for (int j = i*i; j < 10000; j += i)vis[j] = 1;}}}int main(){getPrime();int *ways;int num = 2;while (true){ways = new int[num+1];for (int i = 0; i < num + 1; i++)ways[i] = 0;ways[0] = 1;for (int i = 0; i < 1000; i++){for (int j = prime[i]; j <= num; j++){ways[j] += ways[j – prime[i]];}}//cout << num <<" " << ways[num]<< endl;if (ways[num]>5000)break;elsenum++;}cout << num << endl;system("pause");return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
旅行，不要害怕错过什么，
