我怎样才能找到一个数可以表示为素数之和的方法数?

问题描述

可能的重复:
生成数字的分区

质数和

数字 7 可以用 5 种方式表示为素数之和:

• 2 + 2 + 3
• 2 + 3 + 2
• 2 + 5
• 3 + 2 + 2
• 5 + 2

编写一个程序来计算 n 可以有多少种方式表示为素数之和.你可以假设 n 是一个数字0-100之间.你的程序应该在不到一个小时内打印出答案第二个

示例 1:
给出数字:7 结果:5

示例 2:
给出数字:20 结果:732

示例 3:
给数:80 结果:10343662267187

我已经解决这个问题好几个小时了.我不知道如何从 (n-1) 中得到 n.这是树搜索的前 30 个数字的总和

0 0 0 1 2 2 5 6 10 16 19 35 45 72 105 152 231 332 500 732 1081 1604 2351 3493 5136 7595 1614 4

我以为我找到了最大的链 7 = 5+2 并且以某种方式使用了 5 可以写成 5、3+2、2+3 的知识，但不知何故我需要考虑重复的 2+3+2 替换.

解决方案

查找动态编程，特别是 Wikipedia 的页面和那里的斐波那契数列示例，并考虑如何在此处将其调整到您的问题中.

I've been at this problem for hours. I can't figure out how to get n from (n-1).Here are the sums from the first 30 numbers by a tree search

0 0 0 1 2 2 5 6 10 16 19 35 45 72 105 152 231 332 500 732 1081 1604 2351 3493 5136 7595 11212 16534 24441

I thought I had something with finding the biggest chain 7 = 5+2 and somehow using the knowledge that five can be written as 5, 3+2, 2+3, but somehow I need to account for the duplicate 2+3+2 replacement.

解决方案

Look up dynamic programming, specifically Wikipedia's page and the examples there for the fibonacci sequence, and think about how you might be able to adapt that to your problem here.

这篇关于我怎样才能找到一个数可以表示为素数之和的方法数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！