- 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
ConsoleWrite( _GetPrimeFactors(504) & @CRLF)
ConsoleWrite( _Rad(504) & @CRLF)
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
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
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)