题目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：

1. primes = [True]*100        
   
2. def getPrime(n):
   
3.     primes[0], primes[1] = False, False
   
4.     for (i, prime) in enumerate(primes):
   
5.         if prime:
   
6.             for j in range(i*i,n,i):
   
7.                 primes[j] = False
   
8.     primelist = []
   
9.     for (k, trueprime) in enumerate(primes):
   
10.         if trueprime:
    
11.             primelist.append(k)
    
12.     return primelist
    
13. 
    
14. prime = getPrime(100)
    
15. P=len(prime)
    
16. R=[[0]*P for i in range(100)]
    
17. for k in range(P):
    
18.     R[0][k]=1
    
19. for n in range(0,100,2):
    
20.     R[n][0]=1
    
21. for n in range(2,100):
    
22.     for k in range(1,P):
    
23.         R[n][k]=R[n][k-1]
    
24.         if prime[k]<=n:
    
25.             R[n][k]+=R[n-prime[k]][k]
    
26.     if R[n][-1]>=5000 and not primes[n] or R[n][-1]>=5001:
    
27.         print(n)
    
28.         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

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

1. /*
   
2. 答案：71
   
3. 耗时：0.0001137秒
   
4. */
   
5. #include <iostream>
   
6. #include <cstring>
   
7. using namespace std;
   
8. 
   
9. struct stPolynomial//母函数对应的多项式
   
10. {
    
11.   int a[101];
    
12.   stPolynomial(void)
    
13.   {
    
14.     memset(a, 0, sizeof(a));
    
15.   }
    
16.   stPolynomial(int k)
    
17.   {
    
18.     memset(a, 0, sizeof(a));
    
19.     for (int i = 0; i*k <= 100; ++i)
    
20.       a[i*k] = 1;
    
21.   }
    
22.   stPolynomial(const stPolynomial &p)
    
23.   {
    
24.     memcpy(a, p.a, sizeof(a));
    
25.   }
    
26.   const stPolynomial& operator=(const stPolynomial &p)
    
27.   {
    
28.     memcpy(a, p.a, sizeof(a));
    
29.     return *this;
    
30.   }
    
31.   stPolynomial operator*(const stPolynomial &p) const
    
32.   {
    
33.     stPolynomial x;
    
34.     for (int i = 0; i <= 100; ++i)
    
35.     {
    
36.       for (int j = 0; j <= 100; ++j)
    
37.       {
    
38.         if (i + j <= 100)
    
39.           x.a[i + j] += a[i] * p.a[j];
    
40.       }
    
41.     }
    
42.     return x;
    
43.   }
    
44. };
    
45. 
    
46. int main(void)
    
47. {
    
48.   char cp[100];//构建100以内的素数表
    
49.   memset(cp, 1, 100 * sizeof(char));
    
50.   cp[0] = 0;
    
51.   cp[1] = 0;
    
52.   for (int i = 2; i <= 10; ++i)
    
53.   {
    
54.     if (cp[i] == 0)
    
55.       continue;
    
56.     for (int j = i * i; j < 100; j += i)
    
57.       cp[j] = 0;
    
58.   }
    
59.   stPolynomial f(2);
    
60.   int k = 3;
    
61.   while (true)
    
62.   {
    
63.     stPolynomial g(k);
    
64.     f = f * g;//用所有小于k的素数进行组合
    
65.     if (f.a[k] > 5000)//检查组合数是否大于5000
    
66.       break;
    
67.     //选择下一个素数
    
68.     k += 2;
    
69.     while (cp[k] == 0)
    
70.       k += 2;
    
71.   }
    
72.   cout << k << endl;
    
73.   return 0;
    
74. }

复制代码