素数问题 [英] Problems with prime numbers

问题描述

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

I am trying to write a program to find the largest prime factor of a very large number, and have tried several methods with varying success. All of the ones I have found so far have been unbelievably slow. I had a thought, and am wondering if this is a valid approach:

long number = input;

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

return number;

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

This approach would take an input, and would do the following:

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

200 -> 100 -> 50 -> 25 -> 5 (return)

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

90 -> 45 -> 15 -> 5 (return)

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

It divides currentNum repeatedly by the smallest divisible number (most often 2, or 3) until currentNum itself is prime (there is no divisible prime number less than the squareroot of currentNum), and assumes this is the largest prime factor of the original input.

这总是有效吗？如果没有，有人会给我一个反例吗？

Will this always work? If not, can someone give me a counterexample?

-

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

By very large, I mean about 2^40, or 10^11.

推荐答案

这将始终有效，因为独特的Prime分解定理。

这篇关于素数问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！