并行算法 .NET4.5 .NET4 WPF .NET ASP.NET C#

快速素数分解算法

DrABELL

4.88/5 (21投票s)

2011 年 2 月 8 日

CPOL

4分钟阅读

74456

高效素数分解算法的串行和并行实现

下面描述的快速素数分解算法能够分解大整数（Int64），并相应地进行整数的素数检测。

演示

素数分解算法已在各种Win/Web应用程序[1-4]中实现。下面是一个免费在线素数分解计算器 [1,2]的示例截图，它利用服务器端计算引擎，能够在几秒钟内完成最大的18位数质数（999999999999999989）的素数检测（实际时间取决于Web服务器的流量）。

在线素数分解计算器

图 1. 在线素数分解计算器，演示截图

Windows版素数分解计算器

该算法还为Windows 7/8的教育软件包“Edumatter”中包含的素数分解计算器提供支持（请参见下面的演示快照），可在网上商店[5, 6]购买。

图 2. Windows版素数分解计算器，演示截图

大素数示例

以下是一系列大的（14...18位）素数列表，用于测试/评估目的。

最大的18位素数

999999999999999989
999999999999999967
999999999999999877

最大的17位素数

99999999999999997
99999999999999977
99999999999999961

最大的16位素数

9999999999999937
9999999999999917
9999999999999887

最大的15位素数

999999999999989
999999999999947
999999999999883

最大的14位素数

99999999999973
99999999999971
99999999999959

素数分解算法

下面的代码模块（参见清单1）演示了该算法的实际实现，使用C# (4.0)编写。

列表 1.

//******************************************************************************
// Author           :   Alexander Bell
// Copyright        :   2007-2015 Infosoft International Inc
// Date Created     :   01/15/2007
// Last Modified    :   02/20/2015
// Description      :   Prime Factoring
//******************************************************************************
// DISCLAIMER: This Application is provide on AS IS basis without any warranty
//******************************************************************************
//******************************************************************************
// TERMS OF USE     :   This module is copyrighted.
//                  :   You can use it at your sole risk provided that you keep
//                  :   the original copyright note.
//******************************************************************************
using System;
using System.Collections.Generic;
namespace Infosoft.MathShared
{
    /// <summary>Integers: Properties and Operations</summary>
     public  static partial class Integers
    {
        #region Prime Numbers <100
        private static readonly int[] Primes =
        new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23,
                    29, 31, 37, 41, 43, 47, 53, 59,
                    61, 67, 71, 73, 79, 83, 89, 97 };
        #endregion
         // starting number for iterative factorization
        private const int _startNum = 101;
        #region IsPrime: primality Check
        /// <summary>
        /// Check if the number is Prime
        /// </summary>
        /// <param name="Num">Int64</param>
        /// <returns>bool</returns>
        public static bool IsPrime(Int64 Num){
            int j;
            bool ret;
            Int64 _upMargin = (Int64)Math.Sqrt(Num) + 1; ;
            // Check if number is in Prime Array
            for (int i = 0; i < Primes.Length; i++){
                if (Num == Primes[i]) { return true; }
            }
            // Check divisibility w/Prime Array
            for (int i = 0; i < Primes.Length; i++) {
                if (Num % Primes[i] == 0) return false;
            }
            // Main iteration for Primality check
            _upMargin = (Int64)Math.Sqrt(Num) + 1;
            j = _startNum;
            ret = true;
            while (j <= _upMargin)
            {
                if (Num % j == 0) { ret = false; break; }
                else { j=j+2; }
            }
            return ret;
        }
        /// <summary>
        /// Check if number-string is Prime
        /// </summary>
        /// <param name="Num">string</param>
        /// <returns>bool</returns>
        public static bool IsPrime(string StringNum) {
            return IsPrime(Int64.Parse(StringNum));
        }
        #endregion
        #region Fast Factorization
        /// <summary>
        /// Factorize string converted to long integers
        /// </summary>
        /// <param name="StringNum">string</param>
        /// <returns>Int64[]</returns>
        public static Int64[] FactorizeFast(string StringNum) {
            return FactorizeFast(Int64.Parse(StringNum));
        }
        /// <summary>
        /// Factorize long integers: speed optimized
        /// </summary>
        /// <param name="Num">Int64</param>
        /// <returns>Int64[]</returns>
        public static Int64[] FactorizeFast(Int64 Num)
        {
            #region vars
            // list of Factors
            List<Int64> _arrFactors = new List<Int64>();
            // temp variable
            Int64 _num = Num;
            #endregion
            #region Check if the number is Prime (<100)
            for (int k = 0; k < Primes.Length; k++)
            {
                if (_num == Primes[k])
                {
                    _arrFactors.Add(Primes[k]);
                    return _arrFactors.ToArray();
                }
            }
            #endregion
            #region Try to factorize using Primes Array
            for (int k = 0; k < Primes.Length; k++)
            {
                int m = Primes[k];
                if (_num < m) break;
                while (_num % m == 0)
                {
                    _arrFactors.Add(m);
                    _num = (Int64)_num / m;
                }
            }
            if (_num < _startNum)
            {
                _arrFactors.Sort();
                return _arrFactors.ToArray();
            }
            #endregion
            #region Main Factorization Algorithm
            Int64 _upMargin = (Int64)Math.Sqrt(_num) + 1;
            Int64 i = _startNum;
            while (i <= _upMargin)
            {
                if (_num % i == 0)
                {
                    _arrFactors.Add(i);
                    _num = _num / i;
                    _upMargin = (Int64)Math.Sqrt(_num) + 1;
                    i = _startNum;
                }
                else { i=i+2; }
            }
            _arrFactors.Add(_num);
            _arrFactors.Sort();
            return _arrFactors.ToArray();
            #endregion
        }
        #endregion
    }
}
//******************************************************************************

用于素数检测的并行算法

通过实现并行算法（如下面的代码片段所示），可以获得显著的性能提升。

清单 3. 用于素数检测的并行算法。

#region GetFirstFactorParallel(Int64 Num) algorithm
/// <summary>
/// ===================================================================
/// Copyright(C)2012-2015 Alexander Bell
/// ===================================================================
/// parallel algorithm accepts Int64 Num 
/// and returns either first found not-trivial factor, or number 1.
/// This algo provides performance boost 
/// in comparison to serial implementation on prime factoring of
/// big prime numbers
/// </summary>
/// <param name="Num">Int64</param>
/// <returns>Int64</returns>
internal static Int64 GetFirstFactorParallel(Int64 Num)
{
    // use concurrent stack to store non-trivial factor if found
    ConcurrentStack<Int64> _stack = new ConcurrentStack<Int64>();
            
    // object to specify degrees of parallelism
    ParallelOptions _po = new ParallelOptions();

    try
    {
        // return value initially set to 1
        Int64 _ret = 1;

        // step 1: try to factor on base 2, return if OK
        if (Num % 2 == 0) return 2;

        // step 2: try to factor on base 3, return if OK
        if (Num % 3 == 0) return 3;

        #region parallel algo to find first non-trivial factor if exists

        // set upper limit
        Int64 _upMargin = (Int64)Math.Sqrt(Num) + 1;

        // number of CPU cores
        int _countCPU = System.Environment.ProcessorCount;

        // max degree of parallelism set equal to _cpuCount
        _po.MaxDegreeOfParallelism = _countCPU;

        Parallel.For(0, 2, _po, (i, _plState) =>
        {
            // starting number for inner loops (5 and 7)
            int _seed = 5 + 2 * i;

            // inner loops running in parallel;
            // notice that because input Num was already tested for factors 2 and 3,
            // then increment of 6 is used to speed up the processing,
            // thus in dual core CPU it looks like:
            // 5, 11, 17, 23, 29, etc. in first thread
            // 7, 13, 19, 25, 31, etc, in second thread
            for (Int64 j = _seed; j < _upMargin; j += 6)
            {
                // exit loop if stack contains value
                if (_stack.Count != 0) { break; }

                // check divisibility
                if (Num % j == 0)
                {
                    // push non-trivial factor to ConcurrentStack and exit loop
                    if (_stack.Count == 0) { _stack.Push(j); }
                    break;
                }
            }
        });
        #endregion

        // return the value in ConcurrentStack if exists, or 1
        return (_stack.TryPop(out _ret)) ? _ret : 1;
    }
    catch { throw; }
    finally { _po = null; _stack = null; }

}
#endregion

请注意，由于输入数字Num已经过因子2和3的测试，两个并行运行的内部循环以6为步长递增，以加快处理速度。因此，在双核CPU上，它看起来像：
第一个线程中的5, 11, 17, 23, 29等。
第二个线程中的7, 13, 19, 25, 31等。

关注点

循环计数器递增技术

注意1：对最大的18位数质数（999999999999999989）进行素数检测（即用于确定整数是否为素数的程序）是任何素数分解应用程序软件性能的重要基准。如果计算耗时过长（使用计算能力相对较低的移动平台可能会出现这种情况），则尝试使用较小的数字（也是18位数的质数）： 324632623645234523。

注意 2：在原始代码中，以2为步长递增的实现如下（期望比简单的**i=i+2**或**i+=2**能获得一些性能优势）。

i++; i++;

特别感谢我们的成员AspDotNetDev和irneb，他们对这些不同的增量技术进行了彻底的性能评估，并启发我进一步分析这个问题（尽管与其他计算任务的复杂性/执行时间相比，实际差异可能很小）。以下代码片段已用于对上述三种整数增量技术的性能进行比较。

清单 2. 3种不同整数增量技术的性能测试

//******************************************************************************
// Module           :   Performance test of 3 integer incremental techniques
// Author           :   Alexander Bell
// Date Created     :   02/20/2015
//******************************************************************************
// DISCLAIMER: This module is provide on AS IS basis without any warranty
//******************************************************************************
using System;
using System.Diagnostics;

namespace IncrementEfficiencyTest
{
    class Program
    {
        private const Int64 _max = 1000000000; // 1 billion
        private const int _cycles = 5;

        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();

            // i++ (AVR: 11.907) ***************************************************************************
            Console.Write("{0} on {1}", "i++;i++:", String.Concat(_cycles, " cycles with ", _max, " max: "));
            sw.Restart();
            for (int count = 0; count < _cycles; count++)
            {
                Int64 i = 0;
                while (i < _max) { i++; i++; }
            }
               sw.Stop();
            Console.WriteLine("{0} elapsed.", sw.Elapsed);

            // i=i+2 (AVR: 5.589) _FASTEST **************************************************************
            Console.Write("{0} on {1}", "i=i+2", String.Concat(_cycles, " cycles with ", _max, " max: "));
            sw.Restart();
            for (int count = 0; count < _cycles; count++)
            {
                Int64 i = 0;
                while (i < _max) { i = i + 2; }
            }
            sw.Stop();
            Console.WriteLine("{0} elapsed.", sw.Elapsed);

            // i+=2 (AVR: 5.624 ) | *********************************************************************
            Console.Write("{0} on {1}", "i+=2", String.Concat(_cycles, " cycles with ", _max, " max: "));
            sw.Restart();
            for (int count = 0; count < _cycles; count++)
            {
                Int64 i = 0;
                while (i < _max)  { i += 2;}
            }
            sw.Stop();
            Console.WriteLine("{0} elapsed.", sw.Elapsed);

            Console.ReadKey();
        }
    }
}

该测试使用了与irneb提供的示例代码相同的Stopwatch对象。但是，为了最大限度地减少任何潜在的副作用，它不实现任何可能扭曲时间估计的函数调用，并且运行多个周期（5个周期），随后对多个测试结果进行平均。根据统计结果，将Int64整数加2的最快方法是简单的：i = i+2（整个测试例程用时5.589秒），其次是i += 2（5.625秒），而双重i++;i++;则以11.907秒的性能估计“落后”。相应的修正已应用于原始素数分解算法（现在显示为**i = i+2**）。

通过实现并行素数分解算法，可以实现显著的性能提升，该算法已在Codeproject文章中进行了描述：Edumatter-814: School Math Calculators and Equation Solvers [5]。

多核CPU

素数分解算法的并行实现可以在使用多核CPU的情况下显著提高性能。不建议在单核PC上使用，因为与普通的串行实现相比，线程同步开销可能会导致实际性能下降。

致谢

我想感谢我们的成员AspDotNetDev，特别是irneb，他们花时间努力对不同的整数增量技术进行了性能评估测试（请参考他们相当深思熟虑的评论，其中包含有趣的性能测试结果）。

历史

2015年3月2日：添加了素数分解算法的并行实现示例

参考文献