Введение
Факторизация целых чисел позволяет раскладывать на множители (факторинг) большие числа (Int64) и проверять простоту целых чисел [1,2].
Приведем пример больших (14 ... 18-ти значных) простых чисел, которые можно использовать для тестирования или оценки.
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
Кодовый модуль демонстрирует практическое использование алгоритма, написанного в C# (4.0).
using System;
using System.Collections.Generic;
namespace Infosoft.MathShared
{
///
Integers: Properties and Operations
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
///
/// Check if the number is Prime
///
/// Int64
/// bool
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;
}
///
/// Check if number-string is Prime
///
/// string
/// bool
public static bool IsPrime(string StringNum) {
return IsPrime(Int64.Parse(StringNum));
}
#endregion
#region Fast Factorization
///
/// Factorize string converted to long integers
///
/// string
/// Int64[]
public static Int64[] FactorizeFast(string StringNum) {
return FactorizeFast(Int64.Parse(StringNum));
}
///
/// Factorize long integers: speed optimized
///
/// Int64
/// Int64[]
public static Int64[] FactorizeFast(Int64 Num)
{
#region vars
// list of Factors
List _arrFactors = new List();
// 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
}
}
Точки обзора
Тест на проверку простоты 18-ти значного числа (999999999999999989), т.е. процедура, которая определяет, являются ли целые числа простыми, это лучший способ проверки факторинга программного обеспечения. Если вычисления занимают слишком много времени (например, когда используется мобильная платформа с низким уровнем обработки большого количества численных данных), возьмите меньшее число, но тоже 18-ти значное: 324632623645234523.
Видео курсы по схожей тематике:
Чтобы получить не такую тривиальную запись, как i = i + 2, или i + = 2, необходимо исходный код увеличить в два раза.
i ++; i ++;
Даный фрагмент кода был использован для сравнения производительности трех методов возрастания целых чисел:
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();
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();
}
}
Чтобы минимизировать потенциальные побочные эффекты теста, следует работать в нескольких циклах (5 циклов) с последующей апроксимацией нескольких результатов тестирования и не нужно реализовывать вызовы функций , потому что оценка синхронизации может искажаться. Основываясь на статистических данных, самый быстрый способ увеличения числа Int64 в 2 раза можно достичь через составленное уравнение: i = i + 2 (5,589 сек для всей процедуры тестирования), вместе с i + = 2 (5,625 сек) и удвоением и ++; i ++; "leading from behind" с оценкой производительности в 11,907 сек. Соответствующая поправка была сделана в факторизации первичных чисел (теперь выводится i = i + 2).
Параллельный алгоритм для факторинг-теста
При использовании параллельных алгоритмов факторизации можно значительно увеличить производительность теста.
Параллельне алгоритмы факторизации
region GetFirstFactorParallel(Int64 Num) algorithm
internal static Int64 GetFirstFactorParallel(Int64 Num)
{
// use concurrent stack to store non-trivial factor if found
ConcurrentStack _stack = new ConcurrentStack();
// 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
Бесплатные вебинары по схожей тематике:
Источник: http://www.codeproject.com/Tips/155308/Fast-Prime-Factoring-Algorithm
Статьи по схожей тематике
