Primzahlformel aus dem Untergrund
Verfasst: 16. Feb 2012, 10:39
So Leute ich war lange im Untergrund hoffe es hat was gebracht
hab mir verschiedenstes über Primzahlen angeguckt und alles mögliche an Funktionen probiert, bei wolfram und so aber nie irgendwas gefunden.
Naja jetzt hab ich vllt. wieder was interessantes.
Euklid hat mich drauf gebracht mit seiner Regel für die bst. des größten gemeinsamen Teilers(ggT) zweier Zahlen
Und zwar gehts um eine Primzahlformel, besser gesagt eine Überprüfungsmöglichkeit, ob eine Zahl prim ist oder nicht.
Erstma kurz den Überblick:
Formel : m = P ; wenn f(m)#m -> (1)
Dies bedeutet folgendes:
m = Zahl die man überprüfen will
f(m) = das Produkt aus allen Primzahlen unter der wurzel m bsp.: m= 22 dann f(m) = 1*2*3 ,da Wurzel m = 4,....und draunter die Primzahlen 1,2,3 sind
f(m)#m = den größten gemeinsamen Teiler bestimmen mithilfe eines Satzes von Euklid, der besagt ,dass man die kleinere Zahl immer von der größeren abzieht, zum schluss bleibt x-x=0 dabei ist x schließlich der ggt (größter gemeinsamer Teiler)
bsp: 15 u 6 -> 15-6=9 , 9-6=3, 6-3=3, 3-3=0 ; ggT=3
So jetzt ein bsp. für eine Primzahl. bsp m=41 Wurzel 41= 6,4..... also alle Primzahlen bis 5
somit f(m)=30 , da 1*2*3*5=30
jetzt f(m)#m also -> 41-30=11, 30-11=19, 19-11=8, 11-8=3, 8-3=5, 5-3=2, 3-2=1, 2-1=1, 1-1=0 ggT=1 somit m= Primzahl
theor. kann man sich das Subtrahieren auch verkürzen in dem man die größere Zahl jeweils durch die kleinere Zahl dividiert, dabei wieder den Rest nimmt und fortfährt ,
also bsp: m=101, f(m)= 1*2*3*5*7=210 somit f(m)#f= 210/101=2 rest 8, 101/8=12 rest 5, 8/5=1 rest 3, 5/3=1 rest 2, 3/2=1 rest 1
da man am ende nicht auf x-x=0 wodurch man den ggT bestimmen könnte würd ich beide Verfahren kombinieren.
Erst auf kleine Zahlen runterdividieren, bis wir zu den ersten 10 kommen und dann das substraktionverfahren anwenden.
Ich weiss man müsste mit seeeeehr großen Zahlen operieren, aber falls es klappt ist es immerhin noch besser als die 23variabeln-Formel :p
Kann mal bitte einer checken, ob was an der Formel dran ist. Für meine bisherigen Zahlen hat es gut geklappt
Ich hoffe man hats verstanden ansonsten einfach fragen! m87
hab mir verschiedenstes über Primzahlen angeguckt und alles mögliche an Funktionen probiert, bei wolfram und so aber nie irgendwas gefunden.
Naja jetzt hab ich vllt. wieder was interessantes.
Euklid hat mich drauf gebracht mit seiner Regel für die bst. des größten gemeinsamen Teilers(ggT) zweier Zahlen
Und zwar gehts um eine Primzahlformel, besser gesagt eine Überprüfungsmöglichkeit, ob eine Zahl prim ist oder nicht.
Erstma kurz den Überblick:
Formel : m = P ; wenn f(m)#m -> (1)
Dies bedeutet folgendes:
m = Zahl die man überprüfen will
f(m) = das Produkt aus allen Primzahlen unter der wurzel m bsp.: m= 22 dann f(m) = 1*2*3 ,da Wurzel m = 4,....und draunter die Primzahlen 1,2,3 sind
f(m)#m = den größten gemeinsamen Teiler bestimmen mithilfe eines Satzes von Euklid, der besagt ,dass man die kleinere Zahl immer von der größeren abzieht, zum schluss bleibt x-x=0 dabei ist x schließlich der ggt (größter gemeinsamer Teiler)
bsp: 15 u 6 -> 15-6=9 , 9-6=3, 6-3=3, 3-3=0 ; ggT=3
So jetzt ein bsp. für eine Primzahl. bsp m=41 Wurzel 41= 6,4..... also alle Primzahlen bis 5
somit f(m)=30 , da 1*2*3*5=30
jetzt f(m)#m also -> 41-30=11, 30-11=19, 19-11=8, 11-8=3, 8-3=5, 5-3=2, 3-2=1, 2-1=1, 1-1=0 ggT=1 somit m= Primzahl
theor. kann man sich das Subtrahieren auch verkürzen in dem man die größere Zahl jeweils durch die kleinere Zahl dividiert, dabei wieder den Rest nimmt und fortfährt ,
also bsp: m=101, f(m)= 1*2*3*5*7=210 somit f(m)#f= 210/101=2 rest 8, 101/8=12 rest 5, 8/5=1 rest 3, 5/3=1 rest 2, 3/2=1 rest 1
da man am ende nicht auf x-x=0 wodurch man den ggT bestimmen könnte würd ich beide Verfahren kombinieren.
Erst auf kleine Zahlen runterdividieren, bis wir zu den ersten 10 kommen und dann das substraktionverfahren anwenden.
Ich weiss man müsste mit seeeeehr großen Zahlen operieren, aber falls es klappt ist es immerhin noch besser als die 23variabeln-Formel :p
Kann mal bitte einer checken, ob was an der Formel dran ist. Für meine bisherigen Zahlen hat es gut geklappt
Ich hoffe man hats verstanden ansonsten einfach fragen! m87