|
Autor: mk 06.07.2008 14:28:38 2711 |
|
||
| Standard-Algorithmen |
Bauernmultiplikation
quadratische Gleichung
Eratosthenes
ggt
Bachet
Heron
Potenz
Halbierung
Newton
pi-Bestimmung
Sortieren
Backtracking
|
|
|
Primfaktorzerlegung |
# -*- coding: iso-8859-1 -*-
# Autor: Klaus Merkert, Datum: 2.6.08
def primfac(n):
F = []
while n%2 == 0:
F.append(2)
n = n/2
while n%3 == 0:
F.append(3)
n = n/3
t = 5
diff = 2
while t*t <= n:
while n%t == 0:
F.append(t)
n = n/t
t = t + diff
diff = 6 - diff
if n > 1:
F.append(n)
return F
Für eine Primzahl p gibt es nur die Fälle: 1.Fall: 3∣p+1 oder 2.Fall: 3∤p+1. Im 1.Fall könnte p+2 eine Primzahl sein, da ungerade und nicht durch 3 teilbar. p+4 =p+1 + 3 ist aber wieder durch 3 teilbar, sodass der nächste Primzahl-Kandidat p+6 wäre. Im zweiten Fall muss p+2 durch 3 teilbar sein, weil p und p+1 es nicht waren. Man wird daher p+4 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.
