Факторизация целых чисел - Блог ITVDN
ITVDN: курсы программирования
Видеокурсы по
программированию

Выбери свою IT специальность

Начать бесплатно
ITVDN logo
Видеокурсы по
программированию

Выбери свою IT специальность

Начать бесплатно

Введение

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

КОММЕНТАРИИ И ОБСУЖДЕНИЯ
СТАТЬИ ПО СХОЖЕЙ ТЕМАТИКЕ
ВИДЕО КУРСЫ ПО СХОЖЕЙ ТЕМАТИКЕ

Стань профессионалом, используя все возможности обучения на ITVDN

Стартовый
подписка

Все видео курсы на 3 месяца за 49.99 $

0
Базовый
подписка

Все видео курсы на 6 месяцев за 89.99 $

1
Премиум
подписка

Все видео курсы на 12 месяцев за 169.99 $

2
Notification success