15,793,546 members
Articles / Web Development / ASP.NET
Tip/Trick

# Fast Prime Factoring Algorithm

Rate me:
3 Jul 2015CPOL4 min read 69.1K   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

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.

C#
```//******************************************************************************
// Author           :   Alexander Bell
// Copyright        :   2007-2015 Infosoft International Inc
// Date Created     :   01/15/2007
// Description      :   Prime Factoring
//******************************************************************************
// DISCLAIMER: This Application is provide on AS IS basis without any warranty
//******************************************************************************
//******************************************************************************
//                  :   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])
{
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)
{
_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)
{
_num = _num / i;
_upMargin = (Int64)Math.Sqrt(_num) + 1;
i = _startNum;
}
else { i=i+2; }
}
_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>
/// ===================================================================
/// ===================================================================
/// 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);

}
}
}```

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

Written By
Engineer
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.

 First Prev Next
 Fast algorithm ? YvesDaoust7-Jul-15 1:49 YvesDaoust 7-Jul-15 1:49
 Re: Fast algorithm ? DrABELL7-Jul-15 2:35 DrABELL 7-Jul-15 2:35
 Algorithm name or kind ? Patrice T4-Jul-15 15:26 Patrice T 4-Jul-15 15:26
 Re: Algorithm name or kind ? DrABELL4-Jul-15 15:35 DrABELL 4-Jul-15 15:35
 Easy increase of speed possible Christophe Van Olmen25-Feb-15 4:12 Christophe Van Olmen 25-Feb-15 4:12
 Instead of increasing your divider by 2 every time, you could use the following algorithm: a prime number divided by 30 (LCM of 2, 3 and 5) is one of the folowing: 1,7,11,13,17,19,23,29 (thus eliminating all multiples of 2, 3 and 5) So you only need to check 8 divisors versus 15 in the naive assumption of testing all unpair numbers (after testing the primes smaller than 30). So in pseudocode: for (i=1;i< (sqrt(num)+1)%30;i++) { base = 30*i; if (num % (base+1) ==0) {_arrFactors.Push(base+1);} if (num % (base+7) ==0) {_arrFactors.Push(base+7);} if (num % (base+11) ==0) {_arrFactors.Push(base+11);} if (num % (base+13) ==0) {_arrFactors.Push(base+13);} if (num % (base+17) ==0) {_arrFactors.Push(base+17);} if (num % (base+19) ==0) {_arrFactors.Push(base+19);} if (num % (base+23) ==0) {_arrFactors.Push(base+23);} if (num % (base+29) ==0) {_arrFactors.Push(base+29);} } The next step is looking at remainders of primes modulo 210 (LCM 2, 3, 5 and 7) which elimates some further candidates (but diminishing returns...) such as 7 (mod 210), 49 (mod 210), 77 (mod 210), ...
 Re: Easy increase of speed possible DrABELL2-Mar-15 11:53 DrABELL 2-Mar-15 11:53
 PrimeNumberNow on Windows App Store. TimoKinnunen20-Feb-15 3:55 TimoKinnunen 20-Feb-15 3:55
 Re: PrimeNumberNow on Windows App Store. DrABELL20-Feb-15 5:29 DrABELL 20-Feb-15 5:29
 My vote of 5 [Schnell]Konig18-Feb-13 10:09 [Schnell]Konig 18-Feb-13 10:09
 Re: My vote of 5 DrABELL18-Feb-13 19:44 DrABELL 18-Feb-13 19:44
 Hi AspDotNetDev: 1. I would agree that increment by 2 could... DrABELL23-Feb-11 12:42 DrABELL 23-Feb-11 12:42
 Re: Hi AspDotNetDev:1. I would agree that increment by 2 could... irneb20-Feb-15 1:59 irneb 20-Feb-15 1:59
 Re: Hi AspDotNetDev:1. I would agree that increment by 2 could... irneb20-Feb-15 2:13 irneb 20-Feb-15 2:13
 Re: Hi AspDotNetDev:1. I would agree that increment by 2 could... DrABELL20-Feb-15 3:55 DrABELL 20-Feb-15 3:55
 Re: Hi AspDotNetDev:1. I would agree that increment by 2 could... JesseChisholm4-Jul-15 14:27 JesseChisholm 4-Jul-15 14:27
 Re: Hi AspDotNetDev:1. I would agree that increment by 2 could... DrABELL4-Jul-15 15:27 DrABELL 4-Jul-15 15:27
 I noticed you added two to j (and i) using the ++ operator t... AspDotNetDev23-Feb-11 11:08 AspDotNetDev 23-Feb-11 11:08
 Last Visit: 31-Dec-99 19:00     Last Update: 3-Dec-23 14:21 Refresh 1