Грубая сила, однопоточное разложение на простые множители

Здесь следует рассмотреть следующую функцию, которая может использоваться (относительно быстро) для разложения 64-битного целого числа без знака на его простые множители. Обратите внимание, что разложение на множители не вероятностный (т.е. он точный). Алгоритм уже достаточно быстр, чтобы обнаружить, что число является простым или имеет несколько очень больших множителей за несколько секунд на современном оборудовании.

Вопрос: однопоточное разложение на простые множители На рассмотрение предлагается следующая функция, которая может использоваться (относительно быстро) для разложения 64-битного целого числа без знака на его простые множители. Обратите внимание, что разложение на множители не является вероятностным (то есть ...

Здесь следует рассмотреть следующую функцию, которая может использоваться (относительно быстро) для разложения 64-битного целого числа без знака на его простые множители. Обратите внимание, что разложение на множители не вероятностный (т.е. он точный). Алгоритм уже достаточно быстр, чтобы обнаружить, что число является простым или имеет несколько очень больших множителей за несколько секунд на современном оборудовании.

Вопрос: однопоточное разложение на простые множители На рассмотрение предлагается следующая функция, которая может использоваться (относительно быстро) для разложения 64-битного целого числа без знака на его простые множители. Обратите внимание, что разложение на множители не является вероятностным (то есть ...

Здесь следует рассмотреть следующую функцию, которая может использоваться (относительно быстро) для разложения 64-битного целого числа без знака на его простые множители. Обратите внимание, что разложение на множители не вероятностный (т.е. он точный). Алгоритм уже достаточно быстр, чтобы обнаружить, что число является простым или имеет несколько очень больших множителей за несколько секунд на современном оборудовании.

Вопрос:

На рассмотрение предлагается следующая функция, которая может использоваться (относительно быстро) для разложения 64-битного целого числа без знака на его простые множители. Обратите внимание, что факторинг не является вероятностным (т. Е. Точным). Алгоритм уже достаточно быстр, чтобы обнаружить простое число или несколько очень больших множителей за несколько секунд на современном оборудовании.

Вопрос:

На рассмотрение предлагается следующая функция, которая может использоваться (относительно быстро) для разложения 64-битного целого числа без знака на его простые множители. Обратите внимание, что факторинг не является вероятностным (т. Е. Точным). Алгоритм уже достаточно быстр, чтобы обнаружить простое число или несколько очень больших множителей за несколько секунд на современном оборудовании.

Вопрос: Можно ли внести какие-либо улучшения в представленный алгоритм, сохранив его однопоточность, чтобы он мог быстрее разложить (произвольно) очень большие 64-битные целые числа без знака, желательно без использования вероятностного подхода (например, Миллера-Рабина) для определения простоты ?

// system specific typedef for ulong should go here (or use boost::uint64_t)
typedef unsigned __int64 ulong;
typedef std::vector<ulong> ULongVector;

// Caller needs to pass in an empty factors vector
void GetFactors(ULongVector &factors, ulong num)
{
  // Num has to be at least 2 to contain "prime" factors
  if (num<2)
    return;

  ulong workingNum=num;
  ulong nextOffset=2; // Will be used to skip multiples of 3, later

  // Factor out factors of 2
  while (workingNum%2==0)
  {
    factors.push_back(2);
    workingNum/=2;
  }

  // Factor out factors of 3
  while (workingNum%3==0)
  {
    factors.push_back(3);
    workingNum/=3;
  }

  // If all of the factors were 2s and 3s, done...
  if (workingNum==1)
    return;

  // sqrtNum is the (inclusive) upper bound of our search for factors
  ulong sqrtNum=(ulong) sqrt(double(workingNum+0.5));

  // Factor out potential factors that are greate than or equal to 5
  // The variable n represents the next potential factor to be tested
  for (ulong n=5;n<=sqrtNum;)
  {
    // Is n a factor of the current working number?
    if (workingNum%n==0)
    {
      // n is a factor, so add it to the list of factors
      factors.push_back(n);

      // Divide current working number by n, to get remaining number to factor
      workingNum/=n;

      // Check if we've found all factors
      if (workingNum==1)
        return;

      // Recalculate the new upper bound for remaining factors
      sqrtNum=(ulong) sqrt(double(workingNum+0.5));

      // Recheck if n is a factor of the new working number, 
      // in case workingNum contains multiple factors of n
      continue;
    }

    // n is not or is no longer a factor, try the next odd number 
    // that is not a multiple of 3
    n+=nextOffset;
    // Adjust nextOffset to be an offset from n to the next non-multiple of 3
    nextOffset=(nextOffset==2UL ? 4UL : 2UL);
  }

  // Current workingNum is prime, add it as a factor
  factors.push_back(workingNum);
}

Спасибо

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

Сама по себе функция некрасива и может быть подвергнута рефакторингу, но вопрос в том, как сделать алгоритм быстрее. Так что, пожалуйста, никаких предложений, как сделать функцию более красивой, читаемой, или C ++ иш. Это детская игра. Улучшение этого алгоритма, чтобы он мог быстрее находить (проверенные) факторы, является сложной частью.

Обновление: Potatoswatter пока предлагает несколько отличных решений, обязательно ознакомьтесь с его решением MMX внизу, а также.