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

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

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

    Выбери свою 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

      КОММЕНТАРИИ И ОБСУЖДЕНИЯ

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

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