Грубая сила, однопоточная первичная факторизация

Рассмотрим следующую функцию, которая может быть использована (относительно быстро) для разложения 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-решение внизу.