Click here to Skip to main content
13,091,894 members (65,200 online)
Click here to Skip to main content
Add your own
alternative version

Stats

43.6K views
29 bookmarked
Posted 8 Feb 2011

Fast Prime Factoring Algorithm

, 3 Jul 2015
Rate this:
Please Sign up or sign in to vote.
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

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]:

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.

//******************************************************************************
// 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.

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

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

//******************************************************************************
// 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)

Share

About the Author

DrABELL
President Infosoft International Inc
United States United States
Dr. Alexander Bell is a seasoned full-stack Software Engineer (Win/Web/Mobile). He holds PhD in EE/IT, authored 37 inventions and published 300+ technical articles. Currently focused on HTML5/CSS3, Javascript, .NET/WPF/C#, Angular.js, SQL, 'Big Data', Machine Learning, AI, IoT. Alex participated in App Innovation Contests (AIC 2102/2013) with multiple winning submissions. Portfolio samples:

  1. Real-time NY Bus Tracking Web App (IoT)

  2. Integrated Sensors Hub (IMU) Testing Web Page

  3. Semaphon™ semantic phone num-to-text converter

  4. Educational Web Portal

  5. Free Online NY Payroll Tax Calculator

  6. WebTV powered by YouTube Player powered by .NET API (#1 on Google)

  7. Top-50 Digital Cameras (by iMark-DCAM rating engine)

  8. Pure CSS3 Slide Show

  9. Inflation Calculator

  10. Multilingual Geocoder with Interactive Map

  11. Online Semantic Analyzer (Concordance Calculator)

  12. Advanced CSS3 Table Formatting


You may also be interested in...

Pro

Comments and Discussions

 
QuestionFast algorithm ? Pin
YvesDaoust7-Jul-15 0:49
memberYvesDaoust7-Jul-15 0:49 
AnswerRe: Fast algorithm ? Pin
DrABELL7-Jul-15 1:35
professionalDrABELL7-Jul-15 1:35 
QuestionAlgorithm name or kind ? Pin
ppolymorphe4-Jul-15 14:26
memberppolymorphe4-Jul-15 14:26 
AnswerRe: Algorithm name or kind ? Pin
DrABELL4-Jul-15 14:35
professionalDrABELL4-Jul-15 14:35 
QuestionEasy increase of speed possible Pin
Member 1050612325-Feb-15 3:12
memberMember 1050612325-Feb-15 3:12 
AnswerRe: Easy increase of speed possible Pin
DrABELL2-Mar-15 10:53
professionalDrABELL2-Mar-15 10:53 
QuestionPrimeNumberNow on Windows App Store. Pin
TimoKinnunen20-Feb-15 2:55
memberTimoKinnunen20-Feb-15 2:55 
AnswerRe: PrimeNumberNow on Windows App Store. Pin
DrABELL20-Feb-15 4:29
professionalDrABELL20-Feb-15 4:29 
GeneralMy vote of 5 Pin
[Schnell]Konig18-Feb-13 9:09
member[Schnell]Konig18-Feb-13 9:09 
GeneralRe: My vote of 5 Pin
DrABELL18-Feb-13 18:44
memberDrABELL18-Feb-13 18:44 
GeneralHi AspDotNetDev: 1. I would agree that increment by 2 could... Pin
DrABELL23-Feb-11 11:42
memberDrABELL23-Feb-11 11:42 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
irneb20-Feb-15 0:59
memberirneb20-Feb-15 0:59 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
irneb20-Feb-15 1:13
memberirneb20-Feb-15 1:13 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
DrABELL20-Feb-15 2:55
professionalDrABELL20-Feb-15 2:55 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
JesseChisholm4-Jul-15 13:27
memberJesseChisholm4-Jul-15 13:27 
GeneralRe: Hi AspDotNetDev:1. I would agree that increment by 2 could... Pin
DrABELL4-Jul-15 14:27
professionalDrABELL4-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.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.170813.1 | Last Updated 3 Jul 2015
Article Copyright 2011 by DrABELL
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid