7

我正在尝试编写一个程序来找到一个非常大的数的最大素数，并尝试了几种不同成功的方法。到目前为止，我发现的所有这些都慢得令人难以置信。我有一个想法，想知道这是否是一种有效的方法：

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

这种方法需要输入，并会执行以下操作：

200 -> 100 -> 50 -> 25 -> 5（返回）

90 -> 45 -> 15 -> 5（返回）

它将 currentNum 反复除以最小的可除数（通常是 2 或 3），直到 currentNum 本身是素数（没有小于 currentNum 的平方根的可除素数），并假设这是原始输入的最大素数。

这会一直有效吗？如果没有，谁能给我一个反例？

-

编辑：非常大，我的意思是大约 2^40 或 10^11。

4

6 回答 6

25

该方法会起作用，但会很慢。“你的数字有多大？” 确定使用的方法：

于 2009-12-09T22:19:38.977 回答
17

由于唯一素数分解定理，这将始终有效。

于 2009-12-09T22:10:25.033 回答
3

当然它会起作用（参见Mark Byers 的回答），但对于“非常大”的输入，它可能需要很长时间。您应该注意，您的调用getLowestDivisiblePrimeNumber()隐藏了另一个循环，因此它以 O(N^2) 运行，并且根据您所说的“非常大”的含义，它可能必须在BigNums上运行，这会很慢。

您可以稍微加快速度，注意您的算法永远不需要检查小于最后一个找到的因子。

于 2009-12-09T22:17:26.383 回答
2

您正在尝试找到一个数字的质因数。您提出的建议将起作用，但对于大量用户来说仍然会很慢……您应该对此表示感谢，因为大多数现代安全性都基于这是一个难题。

于 2009-12-09T22:17:25.357 回答
1

从我刚刚做的快速搜索中，已知最快的分解数字的方法是使用椭圆曲线法。

您可以尝试在此演示中输入您的号码：http ://www.alpertron.com.ar/ECM.HTM 。

如果这说服了您，您可以尝试窃取代码（这不好玩，他们提供了指向它的链接！）或在其他地方阅读它的理论。这里有一篇关于它的维基百科文章：http ://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization但我太愚蠢了，无法理解。谢天谢地，这是你的问题，不是我的！:)

于 2009-12-09T22:40:55.410 回答
0

Project Euler 的问题在于，通常有一种明显的蛮力方法来解决问题，这将花费几乎永远的时间。随着问题变得越来越困难，您将需要实施巧妙的解决方案。

解决这个问题的一种方法是使用一个循环，它总是找到一个数字的最小（正整数）因子。当一个数的最小因数是那个数时，你就找到了最大的质因数！

详细算法说明：

您可以通过保留三个变量来做到这一点：

您要考虑的数字 (A) 当前除数存储 (B) 最大除数存储 (C)

最初，让 (A) 成为您感兴趣的数字 - 在这种情况下，它是 600851475143。然后让 (B) 成为 2。有一个条件来检查 (A) 是否可以被 (B) 整除。如果它可整除，则将 (A) 除以 (B)，将 (B) 重置为 2，然后返回检查 (A) 是否可被 (B) 整除。否则，如果 (A) 不能被 (B) 整除，则将 (B) 增加 +1，然后检查 (A) 是否可被 (B) 整除。运行循环直到 (A) 为 1。返回的 (3) 将是 600851475143 的最大素数除数。

有很多方法可以使这更有效——而不是递增到下一个整数，你可以递增到下一个必须的素数整数，而不是保持最大的除数存储，你可以只返回当前数字，当它唯一的除数是本身。但是，我上面描述的算法无论如何都会在几秒钟内运行。

python中的实现如下：-

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

示例：让我们使用上述方法找到 105 的最大素数。

让 (A) = 105. (B) = 2（我们总是从 2 开始），我们还没有 (C) 的值。

(A) 能被 (B) 整除吗？否。将 (B) 增加 +1：(B) = 3。 (A) 可以被 (B) 整除吗？是的。(105/3 = 35)。迄今为止发现的最大除数是 3。令 (C) = 3。更新 (A) = 35。重置 (B) = 2。

现在，（A）可以被（B）整除吗？否。将 (B) 增加 +1：(B) = 3。 (A) 可以被 (B) 整除吗？否。将 (B) 增加 +1：(B) = 4。 (A) 可以被 (B) 整除吗？否。将 (B) 增加 +1：(B) = 5。 (A) 可以被 (B) 整除吗？是的。(35/5 = 7)。我们之前找到的最大除数存储在 (C) 中。(C) 当前为 3。5 大于 3，因此我们更新 (C) = 5。我们更新 (A)=7。我们重置 (B)=2。

然后我们重复 (A) 的过程，但我们将继续递增 (B) 直到 (B)=(A)，因为 7 是素数并且除了它自己和 1 之外没有除数。（我们可以在 (B) 时停止)>((A)/2)，因为整数除数不能大于数字的一半 - 任何数字的最小除数（除 1 之外）都是 2！）

所以此时我们返回 (A) = 7。

试着手工做一些，你就会掌握这个想法

于 2015-07-27T13:03:36.097 回答