题目77：最小的可以以五千种以上的方式写成质数之和的数是多少？

欧拉计划

Prime summations

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

题目：

10 可以以 5 种方式写成质数之和：

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

第一个能够以五千种以上的方式写成质数之和的数是多少？

jerryxjr1220

答案71：

primes = [True]*100        
def getPrime(n):
    primes[0], primes[1] = False, False
    for (i, prime) in enumerate(primes):
        if prime:
            for j in range(i*i,n,i):
                primes[j] = False
    primelist = []
    for (k, trueprime) in enumerate(primes):
        if trueprime:
            primelist.append(k)
    return primelist

prime = getPrime(100)
P=len(prime)
R=[[0]*P for i in range(100)]
for k in range(P):
    R[0][k]=1
for n in range(0,100,2):
    R[n][0]=1
for n in range(2,100):
    for k in range(1,P):
        R[n][k]=R[n][k-1]
        if prime[k]<=n:
            R[n][k]+=R[n-prime[k]][k]
    if R[n][-1]>=5000 and not primes[n] or R[n][-1]>=5001:
        print(n)
        break

芒果加黄桃

jerryxjr1220 发表于 2016-10-16 19:05
答案71：

26行没看懂，老大能帮解释一下么？多谢

jerryxjr1220

芒果加黄桃 发表于 2017-2-17 14:19
26行没看懂，老大能帮解释一下么？多谢

典型的动态规划算法，你把1~10的R的二维数组跟着我的程序画一遍就知道了

芒果加黄桃

jerryxjr1220 发表于 2017-2-17 15:02
典型的动态规划算法，你把1~10的R的二维数组跟着我的程序画一遍就知道了

判断退出条件成立的那个if语句没看明白...

jerryxjr1220

芒果加黄桃 发表于 2017-2-17 15:18
判断退出条件成立的那个if语句没看明白...

你对比一下质数和非质数看看。

najin

用的matlab
结果是
  71

时间已过 0.009884 秒。
>>

guosl

本题其实与上题一样，只是选择的和项只能是素数而已。用递推就不太容易做了，但换成母函数却非常容易，只是在构造母函数时只选择素数来构造就行了。

/*
答案：71
耗时：0.0001137秒
*/
#include <iostream>
#include <cstring>
using namespace std;

struct stPolynomial//母函数对应的多项式
{
  int a[101];
  stPolynomial(void)
  {
    memset(a, 0, sizeof(a));
  }
  stPolynomial(int k)
  {
    memset(a, 0, sizeof(a));
    for (int i = 0; i*k <= 100; ++i)
      a[i*k] = 1;
  }
  stPolynomial(const stPolynomial &p)
  {
    memcpy(a, p.a, sizeof(a));
  }
  const stPolynomial& operator=(const stPolynomial &p)
  {
    memcpy(a, p.a, sizeof(a));
    return *this;
  }
  stPolynomial operator*(const stPolynomial &p) const
  {
    stPolynomial x;
    for (int i = 0; i <= 100; ++i)
    {
      for (int j = 0; j <= 100; ++j)
      {
        if (i + j <= 100)
          x.a[i + j] += a[i] * p.a[j];
      }
    }
    return x;
  }
};

int main(void)
{
  char cp[100];//构建100以内的素数表
  memset(cp, 1, 100 * sizeof(char));
  cp[0] = 0;
  cp[1] = 0;
  for (int i = 2; i <= 10; ++i)
  {
    if (cp[i] == 0)
      continue;
    for (int j = i * i; j < 100; j += i)
      cp[j] = 0;
  }
  stPolynomial f(2);
  int k = 3;
  while (true)
  {
    stPolynomial g(k);
    f = f * g;//用所有小于k的素数进行组合
    if (f.a[k] > 5000)//检查组合数是否大于5000
      break;
    //选择下一个素数
    k += 2;
    while (cp[k] == 0)
      k += 2;
  }
  cout << k << endl;
  return 0;
}