问题标签 [factoring]

假设我们有数字因子，例如 1260：

在 Python 组合中，与这些数字可能的每个子产品（即所有因子，不仅是素因子，因子之和小于max_product ）进行组合的最佳方法是什么？

如果我从主要因素进行组合，我必须重构产品的剩余部分，因为我不知道剩余部分没有组合。

我还可以改进我的除数函数以生成除数对而不是按大小顺序生成除数，但是对于产品高达 12000的数字，我仍然需要这样做。产品必须始终保持不变。

我与除数例程相关联，但看起来不值得努力证明它们适用于我的其他代码。至少我的除数函数明显比 sympy 快：

重用此代码的唯一问题是将除数链接到分解筛或对除数的除数执行某种 itertools.product，我将成对给出，而不是按顺序排序。

示例结果为：

可能我需要一些方法来为较小的除数生成筛子或动态编程解决方案，这些除数可能与它们的除数相关联。看起来很难避免重叠。我确实准备了一个筛子函数，它为每个数字存储最大的素数，以加快分解速度，而不保存每个数字的完整分解……也许可以调整。

更新：因子的总和应该接近产品，因此答案中可能有大量 <= 10 的因子（最多 14 个因子）。

UPDATE2： 这是我的代码，但必须弄清楚如何递归或迭代地对大于 2 的部分进行多次删除，并挖掘词法分区以替换产生重复的跳跃位模式（可怜的命中计数仅用于一个替换，并且不计算在 single_partition 内传递的“单个元素分区”）：

改进我很高兴在非主要因素部分中仅获得最大 5 个因素的因数。我亲手发现最多 5 个相同因子的非递减安排遵循以下形式：

解决方案 我不会从好的解决方案中删除已接受的答案，但它对于这项工作来说过于复杂。从 Project Euler 我只揭示了来自 NZ orbifold 的这个辅助函数，它工作得更快，而且不需要首先使用主要因素：

我的计时装饰器在 4.85 秒内运行 Python 2.7 的问题 88的相关解决方案，并在使用 psyco 的 2.6.6 中找到计数器 3.4 秒优化停止条件后，在没有 psyco 的 2.7 中找到 3.7 秒。在 Python 2.6.6 中，我自己的代码速度从 30 秒（使用接受答案的代码（由我添加的排序删除））到 2.25 秒（2.7 没有 psyco）和782 毫秒（使用 psyco）。

这里有一些软件，它能够将 310 位十进制整数分解为素数吗？有 msieve，我成功地将其用于 120 位分解，但 310 位大于 msieve 的最大允许数量 308 位。

PS：要因式分解的数有2个质因数，p-1,p+1等简单快速的因式分解方法很可能会失败。

更新：似乎只有 GGNFS 可以工作，并且有一些 python 脚本可以自动分解。

我一直在努力同时实现 Dixon 的算法，但结果很差。对于 <~40 位的小数字，它的运行时间大约是我班级中其他实现的两倍，并且在大约 40 位之后，需要更长的时间。

我已尽我所能，但我担心它有一些我找不到的致命问题。

我的代码（相当长）位于此处。理想情况下，该算法将比非并发实现运行得更快。

所以我对递归的想法很陌生，我写了这个简单的代码来分解一个数字（$n）这是代码：

这是代码输出的内容：

所以我的问题是为什么这会在完成之前停止？

嘿，所以我正在制作一个因式分解程序，我想知道是否有人可以给我任何想法，以有效地找到两个数字与指定数字的倍数，并添加到指定的数字。

例如我可能有

(a)(b) = 6

a + b = 5

所以基本上我只需要一种方法来找到 a 和 b 值。在这种情况下，它们将是 2 和 3。

谁能给我任何关于从哪里开始的想法？还必须考虑使用负数。

我试图在一个非常大的虚拟网格中找到某些感兴趣的坐标。这个网格实际上并不存在于内存中，因为尺寸很大。为了这个问题，让我们假设这些维度是(Width x Height) = (Int32.MaxValue x Int32.MaxValue)。

关于网格的已知数据：

• 网格尺寸 = (Int32.MaxValue x Int32.MaxValue).
• 任何给定(x, y)坐标处的值 = X 和 Y 的乘积 = (x * y)。

鉴于上述大量有限数，我需要计算一组坐标，其值为(x * y)的幂e。假设e在这种情况下是 2。

由于循环遍历网格不是一种选择，我考虑过循环遍历：

这给了我们一套独特的权力。我现在需要找出每种力量存在的坐标。让我们来吧2^3=8。如上图所示，8 存在于 4 个坐标中：(8,1), (4,2), (2,4) & (1, 8).

显然，这里的问题是找到数字 8 的多个因数，但这对于更大的数字将变得不切实际。有没有另一种方法来实现这一点，我错过了什么？

• 使用集合是行不通的，因为这些因素不存在于内存中。
• 是否有一种创造性的方法来考虑所讨论的数字将始终是 的幂e？

我正在尝试实现 pollard rho 算法来分解大数。我正在使用 gmp 包。该算法取自“算法简介”。症状是 while 循环永远不会中断。我的想法是我在实施中遗漏了一些东西。

我的代码如下：

}

代码结束

这是我在终止执行之前在终端中得到的一些信息。

我很抱歉打印输出的样子，我有点着急。如果有任何帮助，我将不胜感激。

//海伦

为什么会出现分段错误？我想找到一个数字的所有因素并将它们放在一个向量中。我有另一个函数可以做同样的事情，只是它使用了一个while循环。所以我想我会尝试递归。“i”最初从 1 开始，除非我在 main.cpp 中添加了一些其他值。“cout i”行就在那里，所以我可以看到它失败的地方。

因此，如果我用小于 42800 +/- 100 的数字对其进行测试，则此方法有效。如果我尝试任何大于该数字的数字，它就会停止。调试器说存在分段错误。如果我注释掉 push_back 行，它仍然会在 i 值处崩溃。

但是，如果我从 i = 45000 开始，我可以毫无问题地测试从 45000 到 85000 的数字。高于 85000 就会崩溃。

我想知道为什么会这样。

在 Windows 7 上的 cygwin 中使用 gcc 进行编译。

来自 gdb 的错误消息是：

程序收到信号 SIGSEGV，分段错误。/cygdrive/c/Windows/system32/KERNELBASE.dll 中的 WaitForSingleObjectEx () 中的 0x000007fefcec10d6

我在编程课上完成这个因子生成器时遇到了一些麻烦。它应该取一个数字，并使用 nextFactor 方法打印出所有因子。当我将数字设置为假设 150 时，它会打印出“1 2 3 5”，它应该打印“2 3 5 5”。那么，我应该从这里去哪里？我看过Java - Factor Generator program nextfactor method，但它并没有引起我的任何查询

有人可以告诉我这是否正确吗？如果我做错了，不要去寻找真正的答案，只需要知道我做对了还是需要再试一次。我正在练习的这本书只有奇数问题的答案。

因素完全：

问：8a^2 - 2b^2

我的答案：2(2a + b)(2a - b)