;** zerlegt eine natürliche Zahl in ihre Primfaktoren
;** 27.12.2005 by Triton
;** http://www.silizium-net.de
Graphics 640,480,32,2
AppTitle("Primfaktorenzerlegung")
zahl=1234567890 ;2146654199
Dim primfaktoren(31) ;bis 2^31 gibts max. 31
t1= MilliSecs()
b = primfaktorzerlegung(zahl)
f$ = Str(zahl)+" = "
For pf = 0 To b-1
f$ = f$ + Str(primfaktoren(pf))
If pf < b-1 Then f$ = f$ + " * "
Next
Print f$
Print b+" Primfaktoren gefunden. Dauer: "+Str(MilliSecs()-t1)+" ms"
WaitKey
End
;---
Function primzahl(zahl)
If zahl=1 Or zahl=0 Then Return 0
wurzel=Sqr(zahl)
For a = 2 To wurzel
If zahl Mod a = 0 Then Return 0
Next
Return 1
End Function
;---
Function primfaktorzerlegung(zahl)
;** schreibt die Primfaktoren in array primfaktoren
;** gibt anzahl der Primfaktoren zurück
If primzahl(zahl) = 1 Then
primfaktoren(0) = zahl
Return 1
End If
zahl2=zahl
a=1
While primzahl(zahl2) = 0
a=a+1
If primzahl(a) And zahl2 Mod a = 0 Then
primfaktoren(b) = a
zahl2=zahl2/a
b=b+1
a=1
End If
Wend
primfaktoren(b) = zahl2
b=b+1
Return b
End Function
;---
Function primfaktorzerlegung2(zahl)
;** geht davon aus, dass eine Zahl aus nur 2 Pf besteht
;** -> viel schneller bei diesen speziellen Zahlen
zahl2=zahl
a=1
While b = 0
a=a+1
If primzahl(a) And zahl2 Mod a = 0 Then
primfaktoren(0) = a
b=2
primfaktoren(1)=zahl2/a
Return b
End If
Wend
End Function
|