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

Question

У меня есть число, которое меньше 500 000 000, и я хочу эффективно его разложить на множители. Какой алгоритм вы предлагаете? Примечание: у меня есть ограничение по времени 0,01 сек!

Я только что написал этот код C ++, но он просто ужасен!

void factorize(int x,vector<doubly> &factors)
{
  for(int i=2;i<=x;i++)
    {
      if(x%i==0)
    {
      doubly a;
      a.number=i;
      a.power=0;
      while(x%i==0)
        {
          a.power++;
          x/=i;
        }
      factors.push_back(a);
    }
    }
}

и вдвойне это примерно так:

struct doubly
{
  int number;
  int power;
//and some functions!!

};

просто еще один момент: я знаю, что n не простое число

Answer 1

Как вы, возможно, знаете, факторизация является сложной проблемой. Вы также можете знать, что вам нужно проверять делимость только на простые числа. Небольшая, но хорошо известная подсказка: вам нужно проверить только до квадратного корня из n. Я оставляю вам рассуждения.

Посмотрите на сито Эратосфена. А может быть, вы найдете подсказку в этих вопросах и ответах ? Как насчет этого ?

Если вы хотите сделать это еще быстрее - без полного обмена в пространстве / времени этот ответ - вычислите все простые числа до квадратного корня из 500 000 000 заранее и поместите их в массив. Очевидно, что это нарушается, когда верхний предел растет;)

Answer 2

Если это домашнее задание, я считаю, что вы должны перечитать свой лекционный материал.

В любом случае, вы знаете, что ваш номер составной и очень маленький, это нормально.

Длянаивное пробное деление со всеми числами, вам нужно не более sqrt (500000000) тестов - для наихудшего случая это примерно 22360 раз.Очевидно, что вы можете пропустить четные числа, так как они делятся на 2 (сначала проверьте это).Таким образом, это становится 11180 делений за 0,01 с.Если ваш компьютер может делать 1,1 М делений в секунду, то вы можете просто использовать наивный подход.

Или вы можете составить список простых чисел в автономном режиме, до sqrt (500M), а затем пробную попытку каждогоиз тех.Это еще больше сократит число делений.

Или, если факторы не слишком далеко друг от друга, вы можете попробовать метод Ферма.

Если это не сработает, вы можетепопробуйте использовать роу Полларда и другие.

Или, если это не домашняя работа, переформулируйте проблему, чтобы обойти ограничения (как некоторые предлагали, можете ли вы заранее вычислить факторизованные числа заранее и т.

Answer 3

Вы можете попробовать эвристику Полларда, она подходит для комплексных чисел с относительно небольшими делителями:

Ро Полларда

Answer 4

Факторизуйте все целые числа до 500 000 000 заранее (неважно, как) и сохраняйте коэффициенты в базе данных или в формате записи фиксированной длины.Ваш поиск будет быстрым, и база данных должна соответствовать современному ПК.

Это один из вариантов компромисса между временем и пространством, но вы не сказали, для чего пытаетесь оптимизировать.

В качестве альтернативы рассмотрим алгоритм для GNU coreutils "factor".

Answer 5

Начните изучать алгоритмы .
Какой самый быстрый алгоритм факторизации?