Click here to Skip to main content
15,867,488 members
Articles / Web Development / ASP.NET
Tip/Trick

Fast Prime Factoring Algorithm

Rate me:
Please Sign up or sign in to vote.
4.88/5 (22 votes)
3 Jul 2015CPOL4 min read 70.2K   29   19
Serial and Parallel implementation of efficient Prime Factoriing algorithms

Fast Prime Factoring Algorithm, described below, enables the factoring of large integers (Int64) and correspondingly, the Primality test of integer numbers.

Demo

The Prime factoring algo has been implemented in a variety of Win/Web applications [1-4]. Below is a sample screenshot of the free online Prime Factoring Calculator [1,2], utilizing server-side computation engine capable of running the primality test of the biggest 18-digit prime number (999999999999999989) within seconds (actual time depends on the traffic to the web server).

Online Prime Factoring Calculator

Image 1

Fig .1 Online Prime Factoring Calculator, demo screenshot

Prime Factoring Calculator for Windows

The algoritm is also powers Prime Factoring Calculator included in the educaltion package 'Edumatter' for Windows 7/8 (see the demo snapshot below) available at online store [5, 6]:

Image 2

Fig .2 Prime Factoring Calculator for Windows, demo screenshot

Big Prime samples

Following is a sample list of big (14 ... 18 digits) Prime Numbers useful for testing/evaluation purpose:

biggest 18-digit primes
  • 999999999999999989
  • 999999999999999967
  • 999999999999999877
biggest 17-digit primes
  • 99999999999999997
  • 99999999999999977
  • 99999999999999961
biggest 16-digit primes
  • 9999999999999937
  • 9999999999999917
  • 9999999999999887
biggest 15-digit primes
  • 999999999999989
  • 999999999999947
  • 999999999999883
biggest 14-digit primes
  • 99999999999973
  • 99999999999971
  • 99999999999959

Prime Factoring Algorithms

Following code module (see Listing 1) demonstrates the practical implementation of the algorithm, written in C# (4.0).
 
Listing 1.

C#
//******************************************************************************
// 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
    }
}
//******************************************************************************

Parallel Algoritm for Primality test

Significant performance boost can be obtained by implementing a parallel algoritm as shown in the code snippet below:

Listing 3. Parallel algorithm for primality test.

C#
#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

Notice that because input Num was already tested for factors 2 and 3, two inner loops running in parallel mode are increment by 6 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.

Points of Interest

Loop counter increment technique

Note 1: Primality test (i.e. procedure intended to identify if the integer is a prime number) of the biggest 18-digit prime number (999999999999999989) is a good performance benchmark for any prime factoring application software. If the computation takes too long (it might be a case if using mobile platform with relatively low "number crunching" power), then try the smaller number (also 18 digits prime integer): 324632623645234523.

Note 2: in the original code the increment by 2 was implemented as the following (expected to give some performance addvantages over the trivial i=i+2, or i+=2)

C#
i++; i++;

Special kudos to our members AspDotNetDev and irneb, who did a thorough performance evaluation of these various incremental techniques, and also inspired me to further analyze this issue (even though the practical differences could be rather small in comparison with other computational task's complexity/execution time). The following code snippet has been used for performance comparison of three aforementioned integer incremental techniques:

Listing 2. Performance test of 3 different integer incremental techniques

C#
//******************************************************************************
// 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();
        }
    }
}

The test is using the same Stopwatch object as in the sample code provided by irneb. However, in order to minimize any potential side effects, it does not implement any function calls (which may distort the timing estimates), and is running in multiple cycles (5 cycles) with subsequent averaging of several test results. Based on the statistical outcome, the fastest way to increment the Int64 integer by 2 was found to be a plain straight: i = i+2 (5.589 sec for entire test routine), closely followed by i += 2 (5.625 sec) and the double i++;i++; "leading from behind" with 11.907 sec performance estimate. Corresponding correction has been made to the original prime-factoring algo (it shows now i = i+2).

Significant performance improvement can be achieved by implementing the parallel prime factoring algorithm, described in the Codeproject article: Edumatter-814: School Math Calculators and Equation Solvers [5].

Multi-core CPU

Parallel implementation of the Prime factoring algo leads to significant performance boost in case of using multi-core CPU. It is not recommended for a single-core PC, where the actual performance may degrade due to the thread-synchrinization overhead vs ordinary serial implementation.

Acknowledgement

I would like to thank our members AspDotNetDev and especially irneb for taking time and efforts running the performance evaluation test on different integer incremental techniques (please refer to their rather thoughtfull comments, which include interesting performance test results).

History

3/2/2015: Sample Parallel implementation of prime factoring algorithm added
 
References

  1. Online Prime Factoring Calculator
  2. Mobile Prime Factoring Calculator
  3. Online Fraction Calculator
  4. Mobile Fraction Calculator
  5. Edumatter-814: School Math Calculators and Equation Solvers
  6. 'Edumatter' 5-in-1 School Math Calculators and Equation Solvers for Windows

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Engineer
United States United States
Dr. Alexander Bell (aka DrABell), a seasoned full-stack Software (Win/Web/Mobile) and Data Engineer holds PhD in Electrical and Computer Engineering, authored 37 inventions and published 100+ technical articles and developed multiple award-winning apps (App Innovation Contests AIC 2012/2013 submissions) Alexander is currently focused on Microsoft Azure Cloud and .NET 6/8 development projects.

  1. HTML5/CSS3 graphic enhancement: buttons, inputs
  2. HTML5 Tables Formatting: Alternate Rows, Color Gradients, Shadows
  3. Azure web app: Engineering Calculator VOLTMATTER
  4. Azure: NYC real-time bus tracking app
  5. Quiz Engine powered by Azure cloud
  6. 'enRoute': Real-time NY City Bus Tracking Web App
  7. Advanced CSS3 Styling of HTML5 SELECT Element
  8. Aggregate Product function extends SQL
  9. YouTube™ API for ASP.NET

Comments and Discussions

 
QuestionFast algorithm ? Pin
YvesDaoust7-Jul-15 0:49
YvesDaoust7-Jul-15 0:49 
AnswerRe: Fast algorithm ? Pin
DrABELL7-Jul-15 1:35
DrABELL7-Jul-15 1:35 
QuestionAlgorithm name or kind ? Pin
Patrice T4-Jul-15 14:26
mvePatrice T4-Jul-15 14:26 
AnswerRe: Algorithm name or kind ? Pin
DrABELL4-Jul-15 14:35
DrABELL4-Jul-15 14:35 
QuestionEasy increase of speed possible Pin
Christophe Van Olmen25-Feb-15 3:12
professionalChristophe Van Olmen25-Feb-15 3:12 
AnswerRe: Easy increase of speed possible Pin
DrABELL2-Mar-15 10:53
DrABELL2-Mar-15 10:53 
QuestionPrimeNumberNow on Windows App Store. Pin
TimoKinnunen20-Feb-15 2:55
TimoKinnunen20-Feb-15 2:55 
AnswerRe: PrimeNumberNow on Windows App Store. Pin
DrABELL20-Feb-15 4:29
DrABELL20-Feb-15 4:29 
GeneralMy vote of 5 Pin
[Schnell]Konig18-Feb-13 9:09
[Schnell]Konig18-Feb-13 9:09 
GeneralRe: My vote of 5 Pin
DrABELL18-Feb-13 18:44
DrABELL18-Feb-13 18:44 
Many Thanks!
GeneralHi AspDotNetDev: 1. I would agree that increment by 2 could... Pin
DrABELL23-Feb-11 11:42
DrABELL23-Feb-11 11:42 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
irneb20-Feb-15 0:59
irneb20-Feb-15 0:59 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
irneb20-Feb-15 1:13
irneb20-Feb-15 1:13 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
DrABELL20-Feb-15 2:55
DrABELL20-Feb-15 2:55 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
JesseChisholm4-Jul-15 13:27
JesseChisholm4-Jul-15 13:27 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
DrABELL4-Jul-15 14:27
DrABELL4-Jul-15 14:27 
GeneralI noticed you added two to j (and i) using the ++ operator t... Pin
AspDotNetDev23-Feb-11 10:08
protectorAspDotNetDev23-Feb-11 10:08 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.