Up ist die folgende Funktion, mit der eine 64-Bit-Ganzzahl ohne Vorzeichen (relativ schnell) in ihre Primfaktoren zerlegt werden kann. Es ist zu beachten, dass das Factoring nicht probabalistisch ist (d. H. Es ist genau). Der Algorithmus ist bereits schnell genug, um zu erkennen, dass eine Zahl auf moderner Hardware innerhalb weniger Sekunden eine Primzahl ist oder nur wenige sehr große Faktoren aufweist.

Die Frage: Kann der vorgestellte Algorithmus verbessert werden, während er single-threaded bleibt, so dass er (willkürlich) sehr große 64-Bit-Ganzzahlen ohne Vorzeichen schneller faktorisieren kann, vorzugsweise ohne einen probabalistischen Ansatz (z. B. Miller-Rabin) ) zur Bestimmung der Primalität?

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

Vielen Dan

Edit: Ich habe noch mehr Kommentare hinzugefügt. Der Grund, warum ein Vektor als Referenz übergeben wird, besteht darin, die Wiederverwendung des Vektors zwischen Aufrufen zu ermöglichen und dynamische Zuweisungen zu vermeiden. Der Grund, warum der Vektor in der Funktion nicht geleert wird, besteht darin, die ungerade Anforderung zu berücksichtigen, die aktuellen "num" -Faktoren an Faktoren anzuhängen, die sich bereits im Vektor befinden.

Die Funktion selbst ist nicht hübsch und kann überarbeitet werden, aber die Frage ist, wie der Algorithmus schneller gemacht werden kann. Also bitte keine Vorschläge, wie die Funktion hübscher, lesbarer oder C ++ ish gemacht werden kann. Das ist ein Kinderspiel. Die Verbesserung dieses Algorithmus, damit er (nachgewiesene) Faktoren schneller findet, ist der schwierige Teil.

Update: Potatoswatter hat bis jetzt einige hervorragende Lösungen, sehen Sie sich auch seine MMX-Lösung im unteren Bereich an.