使用轮式分解法确定素数

• 下载源代码 - 26.47 KB
• 下载演示 - 12.42 KB

引言

对于正整数 *n*，我们必须确定 *n* 是否为素数，其中 *n* 很小（即，它可以分配给 C# 中的 ulong 类型）。 因此，*n* 将被限制为小于 2^64-1。 这里提出的算法将通过使用轮式分解法对暴力方法进行一些显著的改进。

背景

素数是数学界感兴趣的数字。 并且，寻找素数似乎是许多数学家的爱好（或职业）。 素数在 RSA 加密算法中也很重要。 甚至还有寻找非常大的素数的奖金。

算法

我们的目标是确定一个正整数是否为素数。 暴力方法看起来像这样

// Warning: Slow code ahead, do not use.
// The brute force way of determining if a number is prime.
public bool IsPrime(ulong primeSuspect)
{
    if (primeSuspect < 2) return false;

    if (primeSuspect == 2) return true;

    for (ulong divisor = 2; divisor < primeSuspect; divisor++)
    {
        // If no remainder after dividing by the divisor
        if (primeSuspect % divisor == 0) 
        {
           return false;  // It is not prime
        }  
    }
    // If we did not find a divisor, it is prime
    return true; 
}

上面的代码效率低下，因为它经常检查一个数字作为可能的除数，而该数字已被消除，因为它是一个较小数字的倍数。 如果已经检查过 2，则无需检查 4 作为除数。 如果已经检查过 3，则无需检查 9 作为除数，依此类推。 另一个问题是它检查所有数字，直到我们的素数候选项作为除数。 我们将首先解决这个问题。

因此，我们对算法的第一个改进是仅搜索我们的素数候选项的因子，直到我们的素数候选项的平方根。 如果有一个大于其平方根的候选因数，那么也必须有一个小于其平方根的因数，这样当这两个因数相乘时，它会给我们原始的候选数。

我们的下一个改进是使用一种称为轮式分解法的方法。 如果我们已经知道所有小于或等于我们候选项平方根的素数，这将是最佳的。 然而，搜索所有这些较小的素数会付出更多计算时间的代价，并否定了我们的大部分收益。 因此，我将使用轮式分解法来加速搜索。

在轮式分解法中，您从前几个素数开始。 在本示例中，我将使用 2、3 和 5，前三个素数，使其简单。（在下载的代码中，我使用了超过前三个素数的数量，这将给我们带来更多的改进。）这给了我们 30 的轮式分解法，即前三个素数的乘积 (2*3*5)。 然后，您创建一个从 1 到 30 的整数列表，并消除列表中所有是 2、3 或 5 的倍数的数字。这给了我们这个列表：{1, 7, 11, 13, 17, 19, 23, 29} 的筛选后的数字。 这些筛选后的数字给我们一个重复的数字模式，并且不是 2、3 或 5 的倍数。因此，如果您将 30 或 60 或 90 等添加到列表中的每个数字，则没有一个可以被 2、3 或 5 整除。 我将对这个筛选后的数字列表进行一个小修改，以使循环更简单。 我将删除 1，并将其添加到列表末尾的 30。 所以现在，我们的数字列表是 {7, 11, 13, 17, 19, 23, 29, 31}。 这是为了我可以执行 pass = 0 并且不必除以 1。

所以，这是程序的核心（为了本文的目的，通过仅使用前三个素数来创建筛子而简化）

private static ulong[] aSieve30 = new ulong[]
         {7, 11, 13, 17, 19, 23, 29, 31};

// Find the first divisor greater than 1 of our candidatePrime.
public static ulong FirstDivisor(ulong candidatePrime)
{
    if (candidatePrime == 0)
        throw new ArgumentException ("Zero is an invalid parameter!");

    // A List of the first three primes
    List<ulong> firstPrimes = 
           new List<ulong>(new ulong[] {2, 3, 5}); 

    WheelFactor = 30;  // The product of the primes in firstPrimes

    if (candidatePrime == 1)
    {  
        // 1 is not considered a prime or a composite number.
        return 0; // So return any number other than 1.
    }
    foreach (ulong prime in firstPrimes)
    {
        if (candidatePrime % prime == 0) return prime;
    }

    // No need to search beyond the square root for divisors
    ulong theSqrt = (ulong)Math.Sqrt((double)candidatePrime); 

    for (ulong pass = 0; pass < theSqrt; pass += WheelFactor)
    {
        foreach (ulong sieve in aSieve30)
        {
            if (candidatePrime % (pass + sieve) == 0)
            {
                  return pass + sieve;
            }
        }
    }
    // If we got this far our number is a prime
    return candidatePrime;
}

public static bool IsPrime(ulong primeSuspect)
{
   if (primeSuspect == 0) return false;
   return (FirstDivisor(primeSuspect) == primeSuspect);
}

从上面的 for 循环中可以看出，它以我们的 WheelFactor 递增，在本例中为 30。 内部循环检查我们筛选列表中的所有 8 个素数。 因此，仅检查 30 个数字中的 8 个，这比暴力方法提高了 73% 以上。 不幸的是，增加我们第一个素数列表中的素数数量对我们的搜索有递减的改进。 下载的代码使用前 8 个素数，这比暴力方法提高了约 83%。

该图说明了 30 的轮式分解。在执行 2、3 和 5 的试除法后，您只需对轮子的白色辐条进行试除法。 轮子的红色辐条已被排除考虑作为可能的除数。

结论

在轮式分解中，通过跳过前几个素数的所有倍数，您可以获得一些良好的性能改进，以确定一个数字是否为素数。

参考

• 田纳西大学马丁分校的素数页面

历史

• 2008 年 11 月 19 日 - 原始提交
• 2009 年 1 月 31 日 - 改进了 BuildSieve() 方法