Primzahlengenerator: Ist die Funktion, die ich in Python programmiert bereits bekannt?
Im folgenden Python Programm werden alle ungeraden Primzahlen generiert.
Es verwendet die senkrechte "Mittellinie" des Pascalschen Dreiecks. Beispielzahlen, die verwendet werden: 2,6,20,70,252,924,3432,.....
2 \ 3 = 2 -> 3 - 2 = 1 -> Prim
6 \ 5 = 1 -> Prim
20 \ 7 = 6 -> 7 - 6 = 1 -> Prim
70 \ 9 = 7 bzw. 9 - 7 = 2 -> Rest ungleich 1 -> nicht Prim
252 \ 11 = 10 -> 11 - 10 = 1 -> Prim
# Programer: Peter Rasinger, Ferlach, Austria, 2005 - 2021
import math
import decimal
decimal.getcontext().prec = 2500000 #250000000000000000
decimal.getcontext()
def is_prim(a4,d4):
f4 = a4 % d4
g4 = d4 - f4
if f4 == 1 or g4 == 1 and d4 != 1:
return(1==1)
else:
return(1==2)
def calc_prim(f3,g3,h3): #f3 = x over x/2 : x \ 2 == 0 ... and g3 == x / 2 ... 6 over 3 = 20 = 6! / (3! * 3!), 8 over 4 = 70
#h3 = steps to calulate (impair numbers)
a3 = f3
b3 = g3
c3 = b3 + 1
if is_prim(a3,c3):
print(c3)
for i3 in range(g3 + 2,(h3 * 2) + g3,2):
r3 = a3 * 4
s3 = r3 // i3
a3 = r3 - s3
b3 = i3
c3 = b3 + 1
if is_prim(a3,c3):
print(c3)
print(math.trunc((math.log(a3) // math.log(10)) + 1)," max digits used")
calc_prim(252,10,100) #252 = 10! / (5! * 5!) ... check 100 impairs ... startvalues for 11
#calc_prim(924,12,100) #924 = 12! / (6! * 6!) ......................... startvalues for 13
#calc_prim(2,2,5)
4 Antworten
Du untersuchst die Zahlen (2n über n), n= 1, 2, ....
Es ist (2n über n) = (2n)! / (n!)²
Und du verwendest das Kriterium von Wilson für p=2n+1, guckst du https://de.wikipedia.org/wiki/Satz_von_Wilson
OK, meine Antwort betraf den theoretischen Hintergrund, zum Algorithmus kann ich nichts sagen.
Ich habe ganz oben (bevor das Programm beginnt) angeführt, welche Zahlen mit diesem Algorithmus berücksichtigt werden können. Die niedrigste Zahl, die berücksichtigt wird, ist die 3 (mit folgendem Startaufruf: calc_prim(2,2,6000), da geht es mit 3 los). Da 2 auch eine Primzahl ist, und diese Zahl nicht mit dem Algorithmus berücksichtigt wird, werden also nur "alle ungeraden Primzahlen" generiert (plus etwaige Ausreißer, wie ralphdieter schon angemerkt hat: 3587 und 5907 - nocheinmal ein Danke an ralphdieter)
hier eine geändert Version:
# Programer: Peter Rasinger, Ferlach, Austria, 2005 - 2022
# programname: primegen.ipynb
# written in Python
# it's possible, that not all calculated numbers are prime or some primes are missed - no guaranty
import math
import decimal
decimal.getcontext().prec = 70 #2500 #increase it, when you get error: InvalidOperation
decimal.getcontext()
def is_prim(a4,d4):
#greetings from Charles Babbage:
#p could also be a sqare from an odd number - check for example p = 25
# Wilson don't work ... 63205303218876 \ 25 = 1, but 63205303218876 \ 25² = 126
#a4 = ((2p - 1) choose (p - 1))
#((2p - 1) choose (p - 1)) \ p² = 1 => prime (mostly?)
#example: d4 = p = 5
#a4 = ((2*5-1)! / (5!*(5-1)!)) = ((10)! choose 5!) / 2 = 3628800 / 120² / 2 = (3628800/14400)/2 = 252/2 = 126
#126 \ 5 = 1? #could be a prime, but there is also to check, if p is a square of an odd number
#126 \ 5² = 1 #here we get (most times?) only primes, if the modulo rest is 1
#a4 = ((2p - 1) choose (p - 1)) = ((2*5-1)! / (5!*(5-1)!)) = (362880 / (120 * 24)) = 126
#now we check for a4 \ 5² = 1? ... 126 \ 25 = 1
f4 = a4 % (d4**2)
return(f4 == 1) #f4 is here 1, when p is prime (no guaranty)
def calc_prim(max):
a3 = 2
i3 = 4
h3 = 2
if max >= 2: print(2)
if max >= 3: print(3)
while i3 <= 6 and i3 < max * 2 + 2:
#overstep all numbers to i3 = 6 (up to primenumber = 3)
r3 = a3 * 4
s3 = r3 // i3
a3 = r3 - s3
i3 = i3 + 2
h3 = h3 + 4
n3 = i3 // 2
while i3 < max * 2 + 2 - 1:
#overstep even-numbers
r3 = a3 * 4
s3 = r3 // i3
a3 = r3 - s3
i3 = i3 + 2
h3 = h3 + 4
#end of overstep even-numbers
n3 = i3 // 2 #n3 is the next odd number
r3 = a3 * 4
#start of odd numbers / only check odd numbers in n3 after division through 2
s3 = r3 // i3
a3 = r3 - s3
m3 = a3 // 2
if is_prim(m3,n3):
print(n3)
i3 = i3 + 2
h3 = h3 + 4
#end of odd numbers
calc_prim(100) #if max + 1 is prime, it will be also printed sometimes
siehe wegen "ungerade Primzahlen": https://de.wikipedia.org/wiki/Primzahl
unter
Euler und das Legendre-SymbolEine einfache Folge aus dem kleinen Satz von Fermat ist die folgende Aussage: Für jede ungerade Primzahl p und jede ganze Zahl...
Also zunächst: Was sollen ungerade Primzahlen sein? Jede Primzahl ist ungerade. Eine Zahl die nicht ungerade ist, ist definitionsmäßig durch 2 teilbar, weshalb sie schon keine Primzahl sein kann.
Dann: Wieso gibst du "1==1" statt true und "1==2" statt false zurück? Sowas macht den Code nur wahnsinnig unleserlich.
Der Algorithmus als solches ist bekannt. Exakt diese Funktion, exakt in Python hat wohl noch nie jemand geschrieben (vor allem mit 1==1 und 1==2 returns...), aber das liegt wohl auch einfach in der Natur der Sache.
Ich habe die Programmierung mit Python im Zuge der Erstellung dieses Programm erst erlernt. Da ich (wie bei sehr vielen Programmiersprachen) gewohnt war, alles klein zu schreiben, habe ich eben auch true und false klein geschrieben. Der Compiler wollte das nicht, also habe ich mit (1==1) für true und (1==2) für false dieses Problem kurzfristig übergangen. Python will eben False und True und nicht false und true.
2 hab ich vollkommen übersehen. Das stimmt dann natürlich.
Ich hab's mal getestet: Du erwischst wirklich jede Primzahl, aber zusätzlich auch die Zahlen 3587=17*211 und 5907=3*11*179. Weitere Ausreißer habe ich bis 2,000,000 nicht gefunden.
Ehrlich gesagt habe ich das Verfahren nicht ganz verstanden. Ich poste mal eine bereinigte Version des Codes (falls das jemand studieren möchte):
def primegen(start, stop):
""" generate primes in [start, stop) """
factors = math.factorial(start&~1) //
math.factorial(start//2)**2
for number in range(start|1, stop, 2):
if factors % number in {1, number-1}:
yield number
factors *= 4
factors -= factors // (number+1)
print("'factors' has", int(math.log(factors, 10)), "digits.")
# calc_prim(252,10,10000) -->
print(*primegen(11, 20011))
Irgendwie scheinst Du den Wert factors effizienter fortschreiben zu wollen als das (p–1)! aus dem Satz von Wilson. Das solltest Du aber genauer beschreiben.
Allerdings landest Du trotzdem schnell bei riesigen Werten. Bei Primzahlen um 1,000,000 hat factors über 300,000 Deziamalstellen. Das macht Deinen Algorithmus langsamer als ein üblicher Primzahlentest. Daher verstehe ich den Sinn des Ganzen nicht.
P.S.: Ungerade Zahlen heißen auf englisch „odd numbers“.
Jetzt sehe ich, dass factors:=(2n)!/n!² in der Schleife tatsächlich nur für (2n+1)->(2n+3) fortgeschrieben wird. Statt
factors *= numbers * (numbers+1) # (numbers-1)! -> (numbers+1)!
factors /= ((numbers+1)/2)**2 # ((numbers-1)/2)!² -> ((numbers+1)/2)!²
rechnest Du kürzer
factors *= 4 * ( 1 - 1/(numbers+1) )
und multiplizierst das aus. So weit, so gut. Nun verwendest Du effektiv den „Satz von Buffi“:
- 2n+1 prim ⇔ (2n)!/n!² ≡ ±1 (mod 2n+1)
Der ist leider falsch, und zwei Gegenbeispiele habe ich ja schon genannt. Somit bleibt eigentlich nur noch offen, ob wenigstens die ⇒-Richtung immer gilt.
Außerdem frage ich mich, was an 3587 und 5907 so besonders ist ...
Irgendwie werd ich aus diesem Programm generell nicht schlau, kann vielleicht daran liegen, dass ich Python nicht wirklich kann aber warum:
Gibst du 1==1 und 1==2 statt true und false zurück?
Wenn r3=s3 ist dann ist doch a3=r3-s3 doch immer 0 in der Schleife.
Die 2-te... (siehe einmal weiter oben)
Ich habe die Programmierung mit Python im Zuge der Erstellung dieses Programm erst erlernt. Da ich (wie bei sehr vielen Programmiersprachen) gewohnt war, alles klein zu schreiben, habe ich eben auch true und false klein geschrieben. Der Compiler wollte das nicht, also habe ich mit (1==1) für true und (1==2) für false dieses Problem kurzfristig übergangen. Python will eben False und True und nicht false und true.
Wenn r3=s3 ist
Das "// i3" dahinter (ganzzahlige Division) wird von GF als Kommentar gesehen und ausgegraut.
Ah ok. Dachte das ist ein Kommentar weil ich eher aus der C++ Ecke komme und daher diese Syntax gewohnt bin.
Ich dachte (auch) an die Kalkulation für n+1, die nicht mit der Falkultät errechnet wird, sondern eben mit der "for i3"-Schleife. Es wird also nicht 2(n+1) über n+1 mittels (2(n+1))! / ((n+1)!)² gerechnet