时间戳

首页 > 解决方案 > 是否有一种方法/算法可以从给定数字的素数生成唯一整数？

python - 是否有一种方法/算法可以从给定数字的素数生成唯一整数？

问题描述

我正在尝试解决以下问题https://open.kattis.com/problems/listgame2 并且我能够成功生成给定数字的所有主要因素，但问题要求我需要获取唯一的列表仅限数字。

例如 - 1099511627776 = 2^40 但由于数字 2 重复了 40 次，所以问题是将 2^40 简化为 2*4*8* .... == 1099511627776 而不重复任何整数以得到该乘积。

我在算法的 Stackoverflow 上发现了一个类似的问题：分解整数 X 以获得尽可能多的不同正整数 (Y1...Yk) 以便 (Y1+1)(Y2+1)...(Yk+1) = X 但没有提供逻辑

上面链接的一个反例是数字 10307264 = 2^6 * 11^5 这应该可能减少到 2 * 4 * 11* 22 * 44 * 121 == 10307264

我不寻求解决方案，而是针对具体逻辑进行讨论以找到最佳解决方案。提前致谢！

标签： pythonalgorithmprimesnumber-theory

解决方案

别再把它们想成唯一的整数了；将它们视为权力的元组。你的第一个例子是 2^40；您必须将其划分40为尽可能多的不同整数。对于这个简单的例子，贪婪的方法让它变得微不足道：你抓住 1，然后 2，......直到剩余的数字不够大，无法在不踩到前一个数字的情况下分开。这是三角形数的简单应用：

`1 2 3 4 5 6 7 8`, and a remainder of 4

...您可以根据需要在较高的数字之间分配（不重复）；您将获得 8 个不同的整数作为分数。例如： 1 2 3 4 6 7 8 9你可能想要的 2 的幂。

对于复数，例如 2^6 11^5，您现在有一对(6, 5)可以划分为不同的对。现在，您可以有 0 个组件，只要没有一对完全为 0。您给定的 5-opint 解决方案是次优的；链接的问题给出了 6，由功率对表示

1 0
2 0
0 1
0 2
1 1
2 1

给我们 6 个 2 和 5 个 11。

这就是多维解决方案派上用场的地方。给定的解决方案是由 2 和 11 的可用小因子（再次贪心）的乘积形成：

{0 1 2} x {0 1 2}

...在每个关键时刻做出成本最低的选择。把它想象成二维空间中的一个格子。从原点附近开始，我们通过晶格向外工作，每次消耗最低成本点。“最低成本”是给我们留下最大选择范围的选择。我将为轴编号并按顺序标记选项：

11 \ 2  0  1  2
  0        A  C
  1     B  E  F  
  2     D

有多种以“最低成本”工作的方法：消耗最少的因子（即最低的元组总和），最大的剩余幂乘积（即我们首先取 2^1，因为剩下 5x5 因子，而不是 4x6 如果我们愿意11^1).

如果递归对您有吸引力，那么您可以编写一个简单的递归例程，遍历 N 维空间的内壳，考虑与已消耗的点相邻的所有元组（包括不合格的原点）。每个选择都会留下一个可分离的、独立的子问题。顺便说一句，证明这个“内壳”足以找到最佳解决方案是微不足道的。

例如，在上面的 (6 5) 示例中，要尝试的两个内壳点是 (1 0) 和 (0 1)，留下 (5 5) 和 (6 4) 的子问题。很容易看出解决方案路径会收敛：我强烈建议，如果您攻击此解决方案，请记住您的结果（动态规划）以避免重复。

这会让你感动吗？

推荐阅读