Primfaktorzerlegung, Radikal eines Integer

  • Hi,
    im EN-Forum war heute eine Fragestellung zur Ermittlung des Radikals eines Integerwertes (Das Radikal einer ganzen Zahl ist das Produkt ihrer unterschiedlichen Primfaktoren). Ich habe dafür eine Autoit-Lösung erstellt (Quelle s.u.), die ich auch hier posten möchte.
    Da es auf Primfaktorzerlegung basiert, habe ich auch die Funktion dazu beigefügt.



    Edit:
    Wen es interessiert, hier mal der Algorithmus zur Primfaktorzerlegung:


    Für eine Primzahl $p sind 2 Fälle möglich:
    1.Fall: 3 ist Element von $p+1 oder
    2.Fall: 3 ist nicht Element von p+1.
    Für den 1.Fall könnte $p+2 eine Primzahl sein, da sie ungerade und nicht durch 3 teilbar ist. $p+4 = $p+1 +3 ist aber wieder durch 3 teilbar, sodass die nächste Primzahl $p+6 wäre.
    In Fall 2 muss $p+2 durch 3 teilbar sein, weil $p und $p+1 es nicht waren. Also ist $p+4 zu untersuchen. $p+5 ist aber wieder durch 3 teilbar, sodass $p+6 es nicht ist. $p+6 kommt als Primzahl-Kandidat in Frage.
    Im ersten Fall sollte man also $p+2 und dann $p+6, im zweiten Fall $p+4 und dann $p+6 untersuchen. Die Primzahlkandidaten haben also abwechselnd eine Differenz von 2 und 4.
    (Quelle: Klaus Merkert, Hohenstaufen-Gymnasium Kaiserslautern, http://www.hsg-kl.de)