Programm zur Primzahlfaktorisierung

Wie kann man ein Programm zur Primzahlfaktorisierung schreiben?

zwutz

du überlegst dir, wie du am effizientesten eine Zahl in die Primfaktoren zerlegst und setzt das entsprechend um

_matze

Hab mal schnell was gebastelt:

#include <iostream>
#include <conio.h>

using namespace std;

int main() {
  long long i=2;
  while(!_kbhit()) {
    for(long long j=2;j<=i;j++) {  
      if(i%j==0) {
        if(j==i) {
          cout << i << endl;
        }else {
          break;
        }
      }
    }
    i++;
  }
  getchar();
}

Ok, wie kann man das effizienter gestalten?

lagalopex

Wikipedia: Faktorisierungsverfahren

Gibt genug Programme, die verschiedene Verfahren (je nach Größenordung) einsetzen um möglichst schnell die Primfaktoren zu bestimmen.
Sowas selbst zu schreiben wird meistens nur in Frust über die eigene Unfähigkeit (=langsames Programm) enden

zwutz

mein Versuch war mal folgender:

int main()
{
    int zahl;
    cin >> zahl;

    if ( zahl < 2 )
    {
        cout << zahl << endl;
    }

    for ( int i = 2; i<= zahl; ++i )
    {
        if ( zahl % i == 0 )
        {
            cout << i << endl;
            zahl /= i;
            i = 2;
        }
    }
}

ist wohl die einfachste, dafür aber auch die langsamste Methode.

eine wirklich effiziente Methode wurde noch nicht gefunden (siehe Wiki-Artikel)

_matze

Ich glaube nicht, dass es Mathefreaks Intention ist, ein fertiges Programm zu nutzen. Es ist entweder eine Schulaufgabe oder er macht es aus eigenem Interesse.

Man muss nicht jedesmal das Rad neu erfinden, aber wenn man es aus Spaß macht, warum nicht?

_matze

zwutz schrieb:

eine wirklich effiziente Methode wurde noch nicht gefunden (siehe Wiki-Artikel)

Ja ja, wir müssen ja hier auch nicht die effizienteste Methode finden, aber ein paar Sachen fallen uns auch ein, oder?

Zum Beispiel sollte man den Schleifendurchlauf beenden, sobald man einen anderen Teiler als 1 oder die Zahl selbst gefunden hat (siehe mein Vorschlag). Außerdem könnte man abbrechen, sobald die Zählvariable größer als die Hälfte der potenziellen Primzahl ist (da wird man wohl nur schwer einen Teiler finden ). Alle gerade Zahlen könnte man auslassen, aber ich bin nicht sicher, ob eine solche Abfrage in jedem Durchlauf auch effizient ist.

Walli

OMG, ne Abfrage macht man da nicht, sondern man inkrementiert die Zählervariable um 2 .

_matze

Walli schrieb:

OMG, ne Abfrage macht man da nicht, sondern man inkrementiert die Zählervariable um 2 .

Hmm, auch wieder wahr...

War ja noch früh...

trivial: Primzahlfaktorisierung

Brutus

Ich haett noch nen simplen Fermat in Scheme rumfliegen, aber das sind auch nur unter 10 Zeilen Dann kann man eigtl. gleich [url=http://en.wikipedia.org/wiki/Shanks'_square_forms_factorization]SQUFOF[/url] nutzen, das ist ein verbesserter Fermat.
Interessant fuer Teiler in der Naehe von sqrt(n)