素数问题
我正在尝试编写一个程序来找到一个非常大的最大素数因子，并尝试了几种不同的成功方法。 到目前为止我发现的所有这些都令人难以置信地缓慢。 我有一个想法，我想知道这是否是一个有效的方法：
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。
由于Unique Prime Factorization定理，这将始终有效。
该方法可行，但速度很慢。 “你的数字有多大？” 确定使用方法：
- 小于2 ^ 16左右：查找表。
- 不到2 ^ 70左右：
阿特金的筛子 。这是更着名的Eratosthenes筛子的优化版本。编辑：在这种情况下， 理查德布伦特修改 Pollard的rho算法可能会更好。 - 小于10 ^ 50： Lenstra椭圆曲线分解
- 小于10 ^ 100： 二次筛
- 超过10 ^ 100： General Number Field Sieve
当然它会起作用（参见Mark Byers的答案 ），但对于“非常大”的输入，它可能需要太长时间。 你应该注意到你对getLowestDivisiblePrimeNumber()调用隐藏了另一个循环，所以它运行在O（N ^ 2），并且根据你的意思“非常大”它可能必须在BigNums上工作，这将是缓慢的。
你可以通过注意你的算法不需要检查比最后找到的因素更小的因子来加快它的速度。
您正试图找到数字的素因子 。 你提出的建议会起作用，但对于大数字来说仍然会很慢……你应该感谢这一点，因为大多数现代安全都是基于这是一个难题。
通过我刚刚进行的快速搜索，使用椭圆曲线方法计算数字的最快的已知方法。
您可以尝试在此演示中输入您的号码： http ： //www.alpertron.com.ar/ECM.HTM 。
如果这说服了你，你可以尝试窃取代码（这没有乐趣，它们提供了一个链接！）或在其他地方阅读理论。 这里有关于它的维基百科文章： http ： //en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization但我太愚蠢了解它。 谢天谢地，这是你的问题，不是我的问题！ 🙂
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）整除吗？ No.增量（B）+1：（B）= 3.（A）是否可以被（B）整除？ 是。 （105/3 = 35）。 到目前为止发现的最大除数是3.令（C）= 3.更新（A）= 35.重置（B）= 2。
现在，（A）是否可以被（B）整除？ No.增量（B）+1：（B）= 3.（A）是否可被（B）整除？ No.增量（B）+1：（B）= 4.（A）是否可以被（B）整除？ No.增量（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。
尝试手工完成其中的一些，你就会明白这个想法