不同的黄金分割数 [英] Number of distinct prime partitions

问题描述

可能重复：
  一些，因为它是素数的部分

我有我的这个家庭作业，坚硬如地狱，在那里我得给定数目的所有不同的素分区。例如，数7具有五个不同的素数的分区（或重新presenting它具有2素分区五种不同的方法）：

I have this homework assignment of mine, hard as hell, where I have to get all the distinct prime partitions of a given number. For example, number 7 has five different prime partitions (or five different ways of representing the 2 prime partitions it has):

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

正如你所看到的，这个数字本身被排除在它的一个主要的情况。我没有打印所有不同的分区，其中只有数

As you can see, the number itself is excluded in the case it's a prime. I don't have to print all the distinct partitions, only the number of them.

所以我有点这个丢失。我已经完全无法产生任何code，但我想我应该从动态规划一种观点接近这一点。我只要求一些提示。有没有人有一个想法？先谢谢了。

So I'm a bit lost with this. I've been completely unable to produce any code, but I think I should approach this from a dynamic programming kind of view. I'm only asking for some hints. Has anyone got an idea? Thanks in advance.

最高输入的号码是100。 此外，程序的运行时间不能超过1秒，并且存储器极限是128MB。

The highest inputted number is 100. Also, the running time of the program cannot exceed 1 second, and the memory limit is 128 MB.

推荐答案

要解决这个你将需要结合三个想法：

To solve this one you are going to need to combine three ideas:

假设给定的数量为n：

• 找到所有素数小于n，如图这里。

动态地从你的主阵列和n计算的子集之和。一些提示是这里和的这里

dynamically calculate the subset sum from your prime array and n. A few hints are here and here

然后，计算出每个不同的排列数回答您从第二步得到的，作为的这里。

then, calculate the number of distinct permutations of each answer you get from step two, as here.

现在，当然，这仅仅是一个暗示。但它会帮助你很大煮了你最后的code。

Now of course, this is just a hint. But it should help you a great deal to cook up your final code.

这篇关于不同的黄金分割数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！