Primfaktorzerlegung, Radikal eines Integer

    • Offizieller Beitrag

    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.

    Spoiler anzeigen
    [autoit]

    ConsoleWrite( _GetPrimeFactors(504) & @CRLF)
    ConsoleWrite( _Rad(504) & @CRLF)

    [/autoit] [autoit][/autoit] [autoit]

    Func _GetPrimeFactors($n)
    Local $F = ObjCreate("System.Collections.ArrayList")
    While Mod($n,2) == 0
    $F.add(2)
    $n = $n/2
    WEnd
    While Mod($n,3) == 0
    $F.add(3)
    $n = $n/3
    WEnd
    Local $t = 5
    Local $diff = 2
    While $t*$t <= $n
    While Mod($n,$t) == 0
    $F.add($t)
    $n = $n/$t
    WEnd
    $t = $t + $diff
    $diff = 6 - $diff
    WEnd
    If $n > 1 Then $F.add($n)
    Local $out = ''
    For $element In $F
    $out &= $element & ','
    Next
    Return StringTrimRight($out, 1)
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func _Radical($n)
    Local $F = ObjCreate("System.Collections.ArrayList")
    While Mod($n,2) == 0
    If Not $F.Contains(2) Then $F.add(2)
    $n = $n/2
    WEnd
    While Mod($n,3) == 0
    If Not $F.Contains(3) Then $F.add(3)
    $n = $n/3
    WEnd
    Local $t = 5
    Local $diff = 2
    While $t*$t <= $n
    While Mod($n,$t) == 0
    If Not $F.Contains($t) Then $F.add($t)
    $n = $n/$t
    WEnd
    $t += $diff
    $diff = 6 - $diff
    WEnd
    If $n > 1 And Not $F.Contains($n) Then $F.add($n)
    Local $out = 1
    For $element In $F
    $out *= $element
    Next
    Return $out
    EndFunc

    [/autoit]

    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)