Factoring eine Reihe

Question

Ich habe eine Reihe bekommt, das weniger als 500 Millionen ist, und ich will es auf eine effiziente Art und Weise faktorisieren. Welcher Algorithmus schlagen Sie vor? Hinweis: Ich habe eine Frist von 0,01 sec haben!

Ich habe dieses C gerade geschrieben ++ Code, aber es ist absolut schrecklich!

void factorize(int x,vector<doubly> &factors)
{
  for(int i=2;i<=x;i++)
    {
      if(x%i==0)
    {
      doubly a;
      a.number=i;
      a.power=0;
      while(x%i==0)
        {
          a.power++;
          x/=i;
        }
      factors.push_back(a);
    }
    }
}

und doppelt so etwas wie folgt aus:

struct doubly
{
  int number;
  int power;
//and some functions!!

};

nur ein weiterer Punkt: Ich weiß, dass n keine Primzahl

Answer 1

Wie Sie vielleicht wissen, Faktorisierung ist ein schwieriges Problem. Vielleicht haben Sie auch wissen, dass Sie nur mit Primzahlen zu Test Teilbarkeit haben. Ein kleiner, aber gut bekannt Hinweis: Sie müssen nur auf die Quadratwurzel von n testen, auf. Ich lasse die Begründung für Sie.

Sehen Sie sich das Sieb des Eratosthenes. Und vielleicht finden Sie einen Hinweis in diese Fragen und Antworten ? Wie wäre es dass ein ?

Wenn Sie dies noch schneller machen wollen - ohne den vollen Handel in Raum / Zeit von diese Antwort - alle Primzahlen berechnen Quadratwurzel von 500 Millionen im voraus und sie in eine Reihe gestellt. Offensichtlich ist diese gebrochen, wenn die obere Grenze wächst;)

Answer 2

Starten Sie studieren die Algorithmen .
Was ist das schnellste Faktorisierung Algorithmus?

Answer 3

Factorize alle ganzen Zahlen zu 500.000.000 im Voraus up (egal wie) und speichern Sie die Faktoren in einer Datenbank oder fester Länge Satzformat. Ihre Lookup wird schnell sein, und die Datenbank sollte auf einem modernen PC passen.

Dies ist ein Ende des Zeit / Raum-Kompromisses, aber man nicht sagen, was Sie versuchen, zu optimieren für.

Alternativ Blick auf den Algorithmus für GNU coreutils "Faktor".

Answer 4

Sie können versuchen rho Heuristik des Pollard, es für komplexe Zahlen mit relativ kleinen Teilern geeignet ist:

Pollard rho

Answer 5

Wenn dies eine Hausaufgabe ist, glaube ich, sollten Sie Ihren Vortrag Material erneut lesen.

Wie auch immer, Sie kennen Ihre Zahl ist zusammengesetzt und sehr klein, das ist in Ordnung.

Für eine naive Versuch Teilung mit allen Zahlen, müssen Sie (500000000) Tests höchstens sqrt -, die für die Worst-Case etwa 22360-mal ist. Sie können natürlich auch Zahlen, da sie sind teilbar mit 2 (Dabei müssen zuerst) überspringen. So dann wird diese 11.180 Teilungen für 0,01 s. Wenn Ihr Computer 1.1 M Teilungen pro Sekunde tun, dann können Sie nur den naiven Ansatz.

Alternativ können Sie eine Liste von Primzahlen off-line machen, bis zu sqrt (500M) und dann jede dieser Untersuchungs versuchen. Dies verringert auf Divisionen einige mehr.

Oder, wenn die Faktoren sind nicht zu weit voneinander entfernt, man konnte Fermats Methode versuchen.

Wenn diese nicht funktionieren, können Sie versuchen Pollard rho und andere zu verwenden.

oder, falls dies nicht Hausaufgaben ist, neu formulieren, das Problem zu arbeiten um die Einschränkungen (wie einige vorgeschlagen haben, können Sie die faktorisierter Zahlen precompute vorher usw.).