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

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

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

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

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

      Факторизация целых чисел

      LIVE ONLINE FRONTEND DEVELOPER Free 4 Ukraine

      Введение

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

      КОММЕНТАРИИ И ОБСУЖДЕНИЯ
      LIVE ONLINE FRONTEND DEVELOPER Free 4 Ukraine

      Пакеты подписки с доступом ко всем курсам и сервисам

      Стартовый
      • Все видеокурсы на 3 месяца
      • Тестирование по 10 курсам
      • Проверка 5 домашних заданий
      • Консультация с тренером 30 мин
      49.99 $
      35.00 $
      Подписка
      Базовый
      • Все видеокурсы на 6 месяцев
      • Тестирование по 16 курсам
      • Проверка 10 домашних заданий
      • Консультация с тренером 60 мин
      89.99 $
      54.00 $
      Подписка
      Премиум
      • Все видеокурсы на 12 месяцев
      • Тестирование по 24 курсам
      • Проверка 20 домашних заданий
      • Консультация с тренером 120 мин
      169.99 $
      85.00 $
      Подписка
      Notification success
      Мы используем cookie-файлы, чтобы сделать взаимодействие с нашими веб-сайтами и услугами простым и значимым.