计算数字最大素数的最佳方法是什么？

我认为最有效的方法如下：

• 查找可以清楚地划分的最低质数
• 检查除法结果是否为质数
• 如果没有，找到下一个最低的
• 转到2.

我基于这个假设，因为它更容易计算出小的素因数。这是对的吗？我还应该考虑其他什么方法？

编辑：我现在意识到，如果有两个以上素数在起作用，我的方法是徒劳的，因为当结果是另外两个素数的乘积时，步骤2失败了，因此需要递归算法。

再次编辑：现在我已经意识到它仍然可以工作，因为最后找到的质数必须是最高的质数，因此，对步骤2中非质数结果进行的任何进一步测试都会产生较小的质数。

解决方案

回答

我认为最好将所有可能小于n的素数存储在某个地方，然后遍历它们以找到最大的除数。我们可以从prime-numbers.org获取质数。

我当然认为电话号码不是太大：)

回答

这可能并不总是更快，但是对于找到一个主要的除数，我们会更加乐观：

• " N"是电话号码
• 如果是素数，则return(N)
• 计算素数直到Sqrt(N)

编辑：在第3步中，我们可以使用Eratosthenes筛子或者Atkins筛子或者任何我们喜欢的筛子，但是筛子本身不会找到最大的主要因素。 (这就是为什么我不选择SQLMenace的帖子作为正式答案的原因...)

回答

不是最快的方法，但是它可以工作！

static bool IsPrime(long num)
    {
        long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
        for (long i = 2; i <= checkUpTo; i++)
        {
            if (num % i == 0)
                return false;
        }
        return true;
    }

回答

n = abs(number);
result = 1;
if (n mod 2 == 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i == 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

有些模数测试是多余的，因为如果所有因子2和3都被删除，则n永远不能除以6. 我们只能为i设置素数，这在其他几个答案中也有显示。

我们实际上可以在此处缠绕Eratosthenes的筛子：

• 首先创建不超过sqrt(n)的整数列表。
• 在for循环中，将直到新sqrt(n)的i的所有倍数都标记为非素数，而使用while循环。
• 将i设置为列表中的下一个素数。

另请参阅此问题。

回答

实际上，有几种更有效的方法来查找大数的因子(对于较小的数，审判分庭工作得相当好)。

如果输入数具有两个非常接近平方根的因子，那么一种非常快的方法称为Fermat因式分解。它利用恒等式N =(a + b)(a b)= a ^ 2 b ^ 2，并且易于理解和实现。不幸的是，它通常不是很快。

分解长达100位数字的最著名方法是二次筛。另外，算法的一部分很容易通过并行处理完成。

我听说过的另一种算法是Pollard的Rho算法。它的效率一般不如Quadratic Sieve，但似乎更容易实现。

一旦决定如何将数字分解为两个因子，这就是我能想到的最快的算法，它可以找到数字的最大质数：

创建一个优先级队列，该队列最初存储数字本身。每次迭代时，我们从队列中删除最高编号，然后尝试将其分为两个因素(当然，不允许1成为这些因素之一)。如果此步骤失败，则该数字为素数，并且我们有答案！否则，我们将两个因素添加到队列中并重复。

回答

最简单的解决方案是一对相互递归的函数。

第一个函数生成所有素数：

• 从一个包含2个和所有大于2的奇数的列表开始。
• 删除所有不是素数的数字。也就是说，没有素数的数字(除了它们本身)。见下文。

第二个函数以递增顺序返回给定数字n的素数因子。策略是尝试将n除以每个可能是其除数的素数：

• 以升序列出所有素数的列表(请参见上文)。
• 如果" p"除以" n"，则" p"是" n"的素数。其他因素是" ps"。
• 否则，" p"不是" n"的素数。

n的最大素数是第二个函数给出的最后一个数字。

为了澄清起见，以下是Haskell中上述代码：

import Control.Monad

-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]

-- Gives the prime factors of its argument
primeFactors = factor primes
  where factor [] n = []
        factor xs@(p:ps) n =
          if p*p > n then [n]
          else let (d,r) = divMod n p in
            if r == 0 then p : factor xs d
            else factor ps n

-- Gives the largest prime factor of its argument
largestFactor = last . primeFactors

回答

所有数字都可以表示为质数的乘积，例如：

102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89

我们可以通过简单地从2开始并继续除以直到结果不是数字的倍数来找到它们：

712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1

使用此方法，我们不必实际计算任何质数：基于我们已经将所有前面的数字尽可能多地分解为数字的事实，它们都将是质数。

number = 712;
currNum = number;    // the value we'll actually be working with
for (currFactor in 2 .. number) {
    while (currNum % currFactor == 0) {
        // keep on dividing by this number until we can divide no more!
        currNum = currNum / currFactor     // reduce the currNum
    }
    if (currNum == 1) return currFactor;    // once it hits 1, we're done.
}

回答

在我看来，给出的算法的第2步并不会是那么有效的方法。我们没有合理的期望，这是首要的。

同样，先前的答案暗示着Eratosthenes筛网是完全错误的。我刚刚编写了两个程序来分解因子123456789. 一个基于Sieve，一个基于以下内容：

1)  Test = 2 
2)  Current = Number to test 
3)  If Current Mod Test = 0 then  
3a)     Current = Current Div Test 
3b)     Largest = Test
3c)     Goto 3. 
4)  Inc(Test) 
5)  If Current < Test goto 4
6)  Return Largest

这个版本比Sieve快90倍。

问题是，在现代处理器上，操作类型的重要性远远小于操作数量，更不用说上面的算法可以在缓存中运行，而Sieve不能。筛子需要执行很多操作才能剔除所有合成数字。

另外，请注意，我在确定因素时将其分开会减少必须测试的空间。

回答

这是我所知道的最佳算法(在Python中)

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors

pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

在最坏的情况下(当输入是质数时)，上述方法在O(n)中运行。

编辑：
如注释中所建议的，以下是O(sqrt(n))版本。这里是代码，再次。

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d*d > n:
            if n > 1: factors.append(n)
            break
    return factors

pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

回答

我的答案是基于三联画的，但是对此做了很多改进。基于以下事实，即2和3以外的所有素数均采用6n-1或者6n + 1的形式。

var largestPrimeFactor;
if(n mod 2 == 0)
{
    largestPrimeFactor = 2;
    n = n / 2 while(n mod 2 == 0);
}
if(n mod 3 == 0)
{
    largestPrimeFactor = 3;
    n = n / 3 while(n mod 3 == 0);
}

multOfSix = 6;
while(multOfSix - 1 <= n)
{
    if(n mod (multOfSix - 1) == 0)
    {
        largestPrimeFactor = multOfSix - 1;
        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
    }

    if(n mod (multOfSix + 1) == 0)
    {
        largestPrimeFactor = multOfSix + 1;
        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
    }
    multOfSix += 6;
}

我最近写了一篇博客文章，解释了该算法的工作原理。

我敢冒险，一种不需要测试原始性(也不需要筛子构造)的方法会比使用那些方法的方法运行得更快。如果真是这样，这可能是最快的算法。