Está em consideração a seguinte função que pode ser usada para (relativamente rapidamente) fatorar um número inteiro não assinado de 64 bits em seus fatores primos. Observe que o fatoração não é probabalístico (ou seja, é exato). O algoritmo já é rápido o suficiente para descobrir que um número é primo ou possui poucos fatores muito grandes em questão de segundos, no hardware moderno.

A pergunta: podem ser feitas melhorias no algoritmo apresentado, mantendo-o com um único encadeamento, para que ele possa fatorar (arbitrariamente) números inteiros de 64 bits não assinados muito grandes mais rapidamente, de preferência sem usar uma abordagem probabalística (por exemplo, Miller-Rabin) para determinar a primalidade?

// 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);
}

obrigado

Editar: adicionei ainda mais comentários. A razão pela qual um vetor é transmitido por referência é permitir que o vetor seja reutilizado entre chamadas e evitar alocações dinâmicas. A razão pela qual o vetor não é esvaziado na função é permitir o requisito ímpar de anexar os fatores "num's" atuais aos fatores já existentes no vetor.

A função em si não é bonita e pode ser refatorada, mas a questão é sobre como tornar o algoritmo mais rápido. Portanto, não há sugestões sobre como tornar a função mais bonita, legível ou em C ++. Isso é brincadeira de criança. Melhorar esse algoritmo, para encontrar fatores (comprovados) mais rapidamente, é a parte mais difícil.

Atualizar:Potatoswatter tem algumas excelentes soluções até agora, verifique também a solução MMX na parte inferior.