Введение

Факторизация целых чисел позволяет раскладывать на множители (факторинг) большие числа (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