问题标签 [factorization]

对于图书馆，我需要将第一个素数存储到限制 L。这个集合必须有 O(1) 查找时间（检查一个数字是否是素数）并且它必须很容易，给定一个数字，找到下一个素数（假设它小于 L）。

鉴于 L 是固定的，生成列表的 Eratostene 筛子就可以了。现在，我使用压缩布尔数组来存储列表，其中仅包含 3 到 L（含）之间奇数的条目。这需要 (L-2)/2 位内存。我希望能够在不使用更多内存的情况下静态增加 L。

是否存在使用较少内存且具有相似属性的数据结构？或者至少有恒定的查找时间？（然后可以枚举奇数，直到我们得到一个素数）

（我写这个的语言是Factor，但这个问题在任何具有内置或易于编程的打包位数组的语言中都是相同的）

我在 Project Euler 做第266 题，经过一番搜索，找到了这种快速查找数字因数的方法。你要做的是找到一个数的质因数的所有排列：这些就是它的因数。

我已经有一个模块来查找数字的主要功率因数，例如：

这基本上表明：2^2 * 7^2 == 196. 从这里我想找到这些幂的所有排列，从而给出 196 的因数：

• (2^0)(7^0) = 1
• (2^1)(7^0) = 2
• (2^2)(7^0) = 4
• (2^0)(7^1) = 7
• (2^1)(7^1) = 14
• (2^2)(7^1) = 28
• (2^0)(7^2) = 49
• (2^1)(7^2) = 98

我想出了以下内容：

但我的问题是factors它不能正常工作。我希望它对每个素数因子的指数的所有可能值进行置换，然后找到给出该因子的乘积。如何修改它以返回n的因子？

我正在尝试学习 F#，所以我访问了Project Euler，我目前正在研究问题 3。

13195 的质因数是 5、7、13 和 29。

数字 600851475143 的最大质因数是多少？

需要考虑的一些事项：

1. 我的首要任务是学习良好的功能习惯。
2. 我的第二个优先事项是我希望它快速高效。

在下面的代码中，我标记了这个问题所涉及的部分。

更新

根据一些反馈，我将代码重构为快 10 倍。

更新

我要感谢大家的建议。这个最新版本是我收到的所有建议的汇编。

我编写了一个程序，试图找到 Amicable Pairs。这需要找到数字的适当除数的总和。

这是我目前的sumOfDivisors()方法：

所以我需要做很多分解，这开始成为我应用程序的真正瓶颈。我在 MAPLE 中输入了一个巨大的数字，它以非常快的速度计算出来。

什么是更快的分解算法之一？

我正在尝试在 C/C++ 中实现 Pollard Rho 整数分解。Google 在这里为我提供了该问题的 Java 实现。

我不太了解 Java，所以我想出了这个。我在 C++ 中的实现适用于大多数情况，但在少数情况下，我使用的不是“9999”。

我知道 C++ 没有 Biginteger 类，所以我不能拥有它在 JAVA 中提供的全部功能，但我想分解 15 位数字，这足以unsigned long long

请指出我的实施中有什么问题。

我正在用 python 模拟我的加密方案，我是它的新用户。

p = 512 位数，我需要为其计算最大素数，我正在寻找两件事：

1. 处理这种大型素数分解的最快代码
2. 可以将 512 位数字作为输入并可以处理的代码。

我在其他语言中看到了不同的实现，我的整个代码都在 python 中，这是我卡住的最后一点。所以让我知道python中是否有任何实现。

请简单解释一下，因为我是 python 的新用户

抱歉英语不好。

编辑（取自以下OP的回答）：

上面的代码适用于“1238162376372637826”（有一点延迟），但将其扩展到

10902610991329142436630551158108608965062811746392 57767545600484549911304430471090261099132914243663 05511581086089650628117463925776754560048454991130443047

让蟒蛇发疯。有什么办法可以像上面一样，我可以立即计算出来吗？

在课堂上我们发现了这个编程问题，目前我们不知道如何解决它。

给出正整数n。已知n = p * q, 其中p和q是素数，p<=q并且|q-k*p|<10^5对于某些给定的正整数k。您必须找到p和q。

输入：

输出：

这不是家庭作业，我们只是想解决一些有趣的问题。如果您有一些想法，请在此处发布，以便我们尝试一下，谢谢。

我正在学习 ruby​​ 并通过解决Project Euler中的问题来练习它。

这是我对问题12的解决方案。

可以对这段代码进行任何改进吗？

当一个可被另一个整除时，数字的位之间是否存在任何关系？36位与9位或4位或12位，或10​​（1010）与5（101），或21（10101）与7（00111）的位序列之间有什么关系？

谢谢。如果某些句子不正确，我很抱歉，但我希望你明白我想要什么。

我正在研究一个需要对整数进行因式分解的 Project Euler 问题。我可以列出作为给定数字因子的所有素数的列表。算术基本定理意味着我可以使用这个列表来推导数字的每个因素。

我目前的计划是获取基本素数列表中的每个数字并提高它的幂，直到它不再是一个整数因子来找到每个素数的最大指数。然后，我将乘以质数-指数对的所有可能组合。

例如，对于 180：

接下来，将这些组合进行到最大指数以获得因子：

所以因子列表 = [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

这是我到目前为止的代码。两个问题：首先，我认为它根本不是 Pythonic。我想解决这个问题。其次，我真的没有 Pythonic 的方式来完成组合的第二步。出于羞耻，我让你免于荒谬的循环。

n 是我们想要分解的数字。listOfAllPrimes 是一个预先计算的最多 1000 万个素数的列表。