Para consideración es la siguiente función que puede usarse para factorizar (relativamente rápido) un entero sin signo de 64 bits en sus factores primos. Tenga en cuenta que la factorización no es probabalística (es decir, es exacta). El algoritmo ya es lo suficientemente rápido como para encontrar que un número es primo o tiene pocos factores muy importantes en cuestión de segundos en el hardware moderno.

La pregunta: ¿Se pueden realizar mejoras en el algoritmo presentado, mientras se mantiene un solo subproceso, de modo que pueda factorizar (arbitrariamente) enteros de 64 bits muy grandes sin signo más rápido, preferiblemente sin usar un enfoque probabalístico (por ejemplo, Miller-Rabin) para determinar la primalidad?

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

Gracias

Editar: he agregado aún más comentarios. La razón por la que se pasa un vector por referencia es para permitir que el vector se reutilice entre llamadas y evitar asignaciones dinámicas. La razón por la que el vector no se vacía en la función, es para permitir el requerimiento extraño de agregar los factores "num" actuales a factores que ya están en el vector.

La función en sí no es bonita y se puede refactorizar, pero la pregunta es cómo hacer que el algoritmo sea más rápido. Entonces, por favor, no hay sugerencias sobre cómo hacer que la función sea más bonita, legible o C ++ ish. Eso es un juego de niños. Mejorar este algoritmo para que pueda encontrar factores (probados) más rápido es la parte difícil.

Actualizar:Agua de patata tiene algunas soluciones excelentes hasta el momento, asegúrese de consultar también su solución MMX cerca del fondo.