题目77：最小的可以以五千种以上的方式写成质数之和的数是多少？
Prime summationsIt 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
第一个能够以五千种以上的方式写成质数之和的数是多少？
答案71：
primes = *100
def getPrime(n):
primes, primes = False, False
for (i, prime) in enumerate(primes):
if prime:
for j in range(i*i,n,i):
primes = False
primelist = []
for (k, trueprime) in enumerate(primes):
if trueprime:
primelist.append(k)
return primelist
prime = getPrime(100)
P=len(prime)
R=[*P for i in range(100)]
for k in range(P):
R=1
for n in range(0,100,2):
R=1
for n in range(2,100):
for k in range(1,P):
R=R
if prime<=n:
R+=R]
if R[-1]>=5000 and not primes or R[-1]>=5001:
print(n)
break jerryxjr1220 发表于 2016-10-16 19:05
答案71：
26行没看懂，老大能帮解释一下么？多谢 芒果加黄桃 发表于 2017-2-17 14:19
26行没看懂，老大能帮解释一下么？多谢
典型的动态规划算法，你把1~10的R的二维数组跟着我的程序画一遍就知道了 jerryxjr1220 发表于 2017-2-17 15:02
典型的动态规划算法，你把1~10的R的二维数组跟着我的程序画一遍就知道了
判断退出条件成立的那个if语句没看明白... 芒果加黄桃 发表于 2017-2-17 15:18
判断退出条件成立的那个if语句没看明白...
你对比一下质数和非质数看看。 用的matlab
结果是
71
时间已过 0.009884 秒。
>> 本帖最后由 guosl 于 2022-1-14 09:53 编辑
本题其实与上题一样，只是选择的和项只能是素数而已。用递推就不太容易做了，但换成母函数却非常容易，只是在构造母函数时只选择素数来构造就行了。{:10_257:}
/*
答案：71
耗时：0.0001137秒
*/
#include <iostream>
#include <cstring>
using namespace std;
struct stPolynomial//母函数对应的多项式
{
int a;
stPolynomial(void)
{
memset(a, 0, sizeof(a));
}
stPolynomial(int k)
{
memset(a, 0, sizeof(a));
for (int i = 0; i*k <= 100; ++i)
a = 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 += a * p.a;
}
}
return x;
}
};
int main(void)
{
char cp;//构建100以内的素数表
memset(cp, 1, 100 * sizeof(char));
cp = 0;
cp = 0;
for (int i = 2; i <= 10; ++i)
{
if (cp == 0)
continue;
for (int j = i * i; j < 100; j += i)
cp = 0;
}
stPolynomial f(2);
int k = 3;
while (true)
{
stPolynomial g(k);
f = f * g;//用所有小于k的素数进行组合
if (f.a > 5000)//检查组合数是否大于5000
break;
//选择下一个素数
k += 2;
while (cp == 0)
k += 2;
}
cout << k << endl;
return 0;
}
页:
[1]