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 回答