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.
using System;
using System.Collections.Generic;
namespace Infosoft.MathShared
{
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
private const int _startNum = 101;
#region IsPrime: primality Check
public static bool IsPrime(Int64 Num){
int j;
bool ret;
Int64 _upMargin = (Int64)Math.Sqrt(Num) + 1; ;
for (int i = 0; i < Primes.Length; i++){
if (Num == Primes[i]) { return true; }
}
for (int i = 0; i < Primes.Length; i++) {
if (Num % Primes[i] == 0) return false;
}
_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;
}
public static bool IsPrime(string StringNum) {
return IsPrime(Int64.Parse(StringNum));
}
#endregion
#region Fast Factorization
public static Int64[] FactorizeFast(string StringNum) {
return FactorizeFast(Int64.Parse(StringNum));
}
public static Int64[] FactorizeFast(Int64 Num)
{
#region vars
List<Int64> _arrFactors = new List<Int64>();
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
internal static Int64 GetFirstFactorParallel(Int64 Num)
{
ConcurrentStack<Int64> _stack = new ConcurrentStack<Int64>();
ParallelOptions _po = new ParallelOptions();
try
{
Int64 _ret = 1;
if (Num % 2 == 0) return 2;
if (Num % 3 == 0) return 3;
#region parallel algo to find first non-trivial factor if exists
Int64 _upMargin = (Int64)Math.Sqrt(Num) + 1;
int _countCPU = System.Environment.ProcessorCount;
_po.MaxDegreeOfParallelism = _countCPU;
Parallel.For(0, 2, _po, (i, _plState) =>
{
int _seed = 5 + 2 * i;
for (Int64 j = _seed; j < _upMargin; j += 6)
{
if (_stack.Count != 0) { break; }
if (Num % j == 0)
{
if (_stack.Count == 0) { _stack.Push(j); }
break;
}
}
});
#endregion
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
using System;
using System.Diagnostics;
namespace IncrementEfficiencyTest
{
class Program
{
private const Int64 _max = 1000000000;
private const int _cycles = 5;
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
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);
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);
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
- Online Prime Factoring Calculator
- Mobile Prime Factoring Calculator
- Online Fraction Calculator
- Mobile Fraction Calculator
- Edumatter-814: School Math Calculators and Equation Solvers
- 'Edumatter' 5-in-1 School Math Calculators and Equation Solvers for Windows