Gesetzmässigkeit bei Primzahlen gefunden?

Neue Frage »

m_OO_m Auf diesen Beitrag antworten »
Gesetzmässigkeit bei Primzahlen gefunden?
Hallo zusammen,

ich wollte hier eine Beobachtung vorstellen, die m.E. auf eine Gesetzmäßigkeit bei Primzahlen hinweist. Wir waren mit einem Verwandten die Tage am Überlegen, ob es so etwas gibt. Da wir beide Ingenieure sind, haben wir nach einer empirischen Lösung gesucht.
Eine Primzahl ist ja eine solche Zahl, die innerhalb von (*) nur durch sich selbst teilbar ist. Wir haben also versucht, die Punktewolke zu zeichnen und daraus irgendwelche Abhängigkeiten zu erkennen, also . Dann nahmen wir die Wolke „schichtenweise“ unter die Lupe – mein Verwandter hatte die Idee, nach etwas wie das Newtonsche Binom zu suchen. Was dabei für einen bestimmten Wert von herauskam, ist klar: , also die Umkehrfunktion.
Innerhalb von ist die Umkehrfunktion ebenfalls eine Punktewolke, die allerdings auch hier symmetrisch ist, die Symmetrieachse ist die Funktion . Hier ein Beispiel mit der Zahl 18 (Bild 1).
[attach]23908[/attach]
Warum das so ist, ist auch klar: wegen des Kommutativgesetzes der Multiplikation. Die Punktewolke für eine Primzahl besteht aus 0 Elementen: und 1 ist ausgeschlossen (s. *). Die Punktewolke für besteht aus einem Punkt, nämlich (Bild 2).
[attach]23910[/attach]
Dann hatte ich die Idee, die Abstände der einzelnen Punkte von der Symmetrieachse zu messen (Bild 3).
[attach]23911[/attach]
Daraus entstand dann folgendes Bild (Bild 4). Primzahlen sind hier gelb.
[attach]23913[/attach]
Eine Primzahl entsteht also dann, wenn innerhalb von keine der im aktuellen Abschnitt des Zahlstrahls enthaltenen Geraden einen Wert produziert (Durch die Symmetrie der Umkehrfunktion braucht man den grau markierten Abschnitt der Punktewolke nicht zu betrachten).
Man könnte es auch mechanisch lösen, mit Zahnrädern mit passender Anzahl Zähne, die von einer Zahnstange in Bewegung gebracht werden. Eine Primzahl liegt vor, wenn sich keines der Zahnräder in der Ausgangsposition befindet (im Bild 5 also keine Primzahl).
[attach]23914[/attach]
Man könnte also im Bereich alle Primzahlen suchen, indem man für die entsprechenden Geraden diese Lücken ermittelt.
Ich habe ein java-Programm geschrieben, das in einer Schleife in Richtung läuft, dabei die Geraden beobachtet und bei entsprechenden Ereignissen die Zahl ausgibt. (Die Denke ist im Bild 4 als binäre Logik abgebildet, s. rechten Rand). Die Ergebnisse passen.
Aber ich habe keine Idee, wie sich das in Form einer Funktion aufstellen lässt… Das war auch die Frage, die in meinem ersten Thread enthalten war.
Was meint ihr?
m_OO_m Auf diesen Beitrag antworten »
... das Progrämmel
s. Anhang. Ausgabe:

5
7
Führe neue Gerade ein: Startpunkt = 9; Periode: 2; insg. 2
11
13
Führe neue Gerade ein: Startpunkt = 16; Periode: 3; insg. 3
17
19
23
Führe neue Gerade ein: Startpunkt = 25; Periode: 4; insg. 4
29
31
Führe neue Gerade ein: Startpunkt = 36; Periode: 5; insg. 5
37
41
43
47
Führe neue Gerade ein: Startpunkt = 49; Periode: 6; insg. 6
53
59
61
Führe neue Gerade ein: Startpunkt = 64; Periode: 7; insg. 7
67
71
73
79
Führe neue Gerade ein: Startpunkt = 81; Periode: 8; insg. 8
83
89
97
Mystic Auf diesen Beitrag antworten »
RE: ... das Progrämmel
Ja, da haben schon die alten Griechen darüber nachgedacht, wie man auf schnellstem Wege zu den Primzahlen kommen könnte und das sog. Sieb des Eratosthenes ist auch heute noch vom Laufzeitverhalten her unschlagbar, wenn man schnell eine kleine Primzahltabelle anlegen will... Ich sagte "kleine", denn bis sagen wir 10 Mill. sollte das noch locker auf jedem PC möglich sein, bei einer oberern Grenze von einer Miiliarde dürfte es bereits problematisch sein, und darüber hinaus geht der Rechner sicher vom Speicherplatzbedarf her bald in die Knie...

Ok, wo liegen die Gemeinsamkeiten, wo die Unterschiede zu besagtem Sieb?... Angenommen wir wollen die zusammengesetzen Zahlen im Bereich



aussieben... Eratosthenes hätte da zuerst die Vielfachen von 2 bis höchstens 2*5 ausgesiebt, also



und das sind auch deine Zahlen auf der ersten Linie... Er hätte fortgesetzt mit den Zahlen



also deinen Zahlen bis 3*5 auf der 2. Linie... Aber er hätte NICHT deine Zahlen auf der 3.Linie angefasst, denn diese sind durch 4, also erst recht durch 2 teilbar, und wären daher bereits ausgesiebt worden, sondern er hätte gleich mit deiner 4. Linie bis 5*5, also dann der einzigen Zahl



weitergemacht... Die verbleibenden, d.h., nicht ausgesiebte Zahlen 29 und 31, sind dann tatsächlich prim...

Was waren doch diese alten Griechen schon für schlaue Kerlchen, was? Augenzwinkern (Manche sagen ja, das sind sie heute noch, aber das ist ein ganze anderes Thema! Big Laugh )
m_OO_m Auf diesen Beitrag antworten »
RE: ... das Progrämmel
ja-ja, Sieb des Eratosthenes... Es geht dabei ja darum, aus einem best. Zahlenbereich das Mehrfache anderer Zahlen so lange wegzustreichen, bis Primzahlen übrig bleiben (sie können nach dem Verfahren nicht weggestrichen werden).

Lass mich bitte den Vergleich aus Sicht der Programmierung machen. Für ein etwas modifiziertes Erastosthenes - Verfahren benötigt man eine Liste der bereits bekannten Primzahlen. Jede neue Zahl wird darauf geprüft, ob sie durch ein Element dieser Liste teilbar ist. Wenn nein, ist es eine neue Primzahl.

Das Verfahren geht tatsächlich in die Knie, da die Liste der Primzahlen immer länger wird. Ich kam mit einem solchen Programm in 30 Minuten bis ca. 250.000

Mein Verfahren erreichte in der gleichen Zeit die Zahl 9.000.000. Es verwendet außerdem keine Division, es beobachtet nur die "Zyklen" der unterschiedlichen Geraden - ist im Programm deutlich ersichtlich.

Mir geht es außerdem nicht darum, per Ausschlussverfahren Zahlen zu suchen. Das Programm soll lediglich zeigen, dass dieses Verfahren, das eigentlich gar nicht mit Primzahlen hantiert, dennoch Primzahlen ermittelt.

Die Vorgehensweise in eine Gleichung umzuwandeln, die z.B. für einen bestimmten Zahlenbereich alle Primzahlen als Lösungsmenge liefert, übersteigt leider meine Mathe-Kenntnisse.
m_OO_m Auf diesen Beitrag antworten »
RE: ... das Progrämmel
Zitat:
Original von Mystic
...Aber er hätte NICHT deine Zahlen auf der 3.Linie angefasst, denn diese sind durch 4, also erst recht durch 2 teilbar, und wären daher bereits ausgesiebt worden...


Das ist wohl wahr - vorbehaltlich der o.h. Unterschiede zu Eratosthenes Augenzwinkern

Die Programmänderung muss ich noch machen - melde mich dann.
Mystic Auf diesen Beitrag antworten »
RE: ... das Progrämmel
Zitat:
Original von m_OO_m
ja-ja, Sieb des Eratosthenes... Es geht dabei ja darum, aus einem best. Zahlenbereich das Mehrfache anderer Zahlen so lange wegzustreichen, bis Primzahlen übrig bleiben (sie können nach dem Verfahren nicht weggestrichen werden).

Lass mich bitte den Vergleich aus Sicht der Programmierung machen. Für ein etwas modifiziertes Erastosthenes - Verfahren benötigt man eine Liste der bereits bekannten Primzahlen. Jede neue Zahl wird darauf geprüft, ob sie durch ein Element dieser Liste teilbar ist. Wenn nein, ist es eine neue Primzahl.

Sorry, dann reden wir von verschiedenen Dingen... Inwiefern braucht das Sieb des Eratosthenes eine Liste von Primzahlen? Das braucht es an keiner Stelle... Wohl aber kommt eine Liste von Primzahlen zum Schluss heraus, das ist aber ein kleiner, aber feiner Unterschied... Augenzwinkern

Zitat:
Original von m_OO_m
Das Verfahren geht tatsächlich in die Knie, da die Liste der Primzahlen immer länger wird. Ich kam mit einem solchen Programm in 30 Minuten bis ca. 250.000

Das ist jetzt nicht dein Ernst, oder? Bis 250.000 sollte die Rechenzeit noch im Millisekundenbereich liegen... geschockt

Zitat:
Original von m_OO_m
Mein Verfahren erreichte in der gleichen Zeit die Zahl 9.000.000. Es verwendet außerdem keine Division, es beobachtet nur die "Zyklen" der unterschiedlichen Geraden - ist im Programm deutlich ersichtlich.

Ohne es jetzt probiert zu haben, sollte das in weniger als 1 min zu schaffen sein (bezieh mich da jetzt allerdings auf C#... Obwohl es normalerweise klar schneller als Java sein sollte, glaube ich dennoch nicht, dass da jetzt so Welten dazwischenliegen...)

Zitat:
Original von m_OO_m
Mir geht es außerdem nicht darum, per Ausschlussverfahren Zahlen zu suchen. Das Programm soll lediglich zeigen, dass dieses Verfahren, das eigentlich gar nicht mit Primzahlen hantiert, dennoch Primzahlen ermittelt.

Ja, das ist beim Sieb des Eratosthenes auch der Fall, wie schon erwähnt, also ist das nichts Neues...

Zitat:
Original von m_OO_m
Die Vorgehensweise in eine Gleichung umzuwandeln, die z.B. für einen bestimmten Zahlenbereich alle Primzahlen als Lösungsmenge liefert, übersteigt leider meine Mathe-Kenntnisse.

Nicht nur deine, glaube mir, nicht nur deine... Big Laugh
 
 
HAL 9000 Auf diesen Beitrag antworten »

Nur mal das Beispiel eines Board-Threads, wo Eratosthenes erfolgreich angewandt wurde:

Primzahl-Algorithmus gesucht

Und die Rechenzeiten liegen eher in den von Mystic angegebenen Dimensionen:

Alle Primzahlen unterhalb ca. in ca. einer Stunde auf einem mittlerweile betagten Rechner... Augenzwinkern
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Nur mal das Beispiel eines Board-Threads, wo Eratosthenes erfolgreich angewandt wurde:

Primzahl-Algorithmus gesucht

Und die Rechenzeiten liegen eher in den von Mystic angegebenen Dimensionen:

Alle Primzahlen unterhalb ca. in ca. einer Stunde auf einem mittlerweile betagten Rechner... Augenzwinkern

Ja, danke für den Hinweis auf den in vielerlei Hinsicht hochinteressanten Thread... Augenzwinkern

Insbesondere dürfte damit klar sein, dass ich mit meinen Schätzungen oben nicht weit danebenliege, wenn ich mich auch in Anbetracht der gigantischen Datenmengen jetzt nicht getraut hätte zu sagen, dass man selbst auf einem PC noch bis in den Bereich kommen kann (geschweige denn in weniger als einer Stunde!)...
m_OO_m Auf diesen Beitrag antworten »
RE: ... das Progrämmel
Zitat:
Original von m_OO_m
...Das Verfahren geht tatsächlich in die Knie, da die Liste der Primzahlen immer länger wird. Ich kam mit einem solchen Programm in 30 Minuten bis ca. 250.000


Da habe ich tatsächlich Quatsch erzählt. Die ersten 10 Minuten brachten es bis ca. 800.000 und fanden ca. 65.000 Primzahlen. Bei meinem "ungefilterten" Verfahren sind es entsprechend 3.000.000 und 220.000, beim "gefilterten" 11.000.000 und 730.000 Primzahlen.

Dass Eratosthenes keine Liste der Primzahlen braucht, stimmt, solange Du einen Bereich mit Zahlen von 1 bis n hast, mit dem Du arbeitest. Dort kannst Du tatsächlich von vorne anfangen und Mehrfaches so lange streichen, bis "im Sieb" Primzahlen bleiben. Wenn aber anstelle von n steht, geht das so nicht.
m_OO_m Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Alle Primzahlen unterhalb ca. in ca. einer Stunde auf einem mittlerweile betagten Rechner... Augenzwinkern


Ich wollte, ehrlich gesagt, nicht über das Programm reden, sondern über die Herangehensweise. Ich wollte auch nicht über die Geschwindigkeit von C# gegen java, C++ und so weiter diskutieren. Und auch nicht darüber, ob ich als Programmierer was tauge.

Meine Absicht ist zu sagen: es gibt (?) ein gewisses Rhythmus beim Entstehen von Primzahlen, das sich wie oben beschrieben darstellen läßt. Primzahlen sind nicht chaotisch von 1 bis unendlich verteilt, es gibt eine Gesetzmässigkeit. Das Programm war eigentlich mehr als eine Illustration dazu gedacht, um jenseits von 30 zu kommen.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von m_OO_m
[quote]Original von HAL 9000
Meine Absicht ist zu sagen: es gibt (?) ein gewisses Rhythmus beim Entstehen von Primzahlen, das sich wie oben beschrieben darstellen läßt. Primzahlen sind nicht chaotisch von 1 bis unendlich verteilt, es gibt eine Gesetzmässigkeit. Das Programm war eigentlich mehr als eine Illustration dazu gedacht, um jenseits von 30 zu kommen.

Aha, das war nach deinem Eingangsposting bisher durchaus nicht klar... Aber da du bisher - wenn auch noch so vage - auf keine Gesetzmäßigkeit in der Primzahlverteilung hingewiesen hast, gibt's auch nichts, was man beweisen oder durch ein Gegenbeispiel widerlegen könnte... traurig

Und Gesetzmäßigkeiten in der Primzahlverteilung gibt's genug, wenn auch nur im Großen, also statistisch gesehen, schau mal hier ... Und es gibt sogar Gesetzmäßigkeiten im Kleinen, sie haben aber alle die Eigenschaft, dass man "mehr" in sie hineinstecken muss, als am Ende dabei herauskommt, z.B., die exakte Verteilung der Nullstellen der Riemannschen Zeta-Funktion im kritischen Streifen...
m_OO_m Auf diesen Beitrag antworten »

ok... es gibt eine Gesetzmässigkeit, die für alle Primzahlen gilt. Übrigens, zum Erastothenes: wenn ich Wikipedia richtig verstanden habe, funktioniert das Verfahren nur für Bereiche 1 bis n. Denn wenn wir z.B. den Bereich 6 bis n betrachten, ist 6 nach Erastothenes eine Primzahl (denn welche Primzahlen davor enthalten waren, "weiss" ja keiner).

Wenn wir die Ausführungen vom oben heranziegen, haben wir für
(1) ist ca. 2,45. Periode und Startpunkt der letzten "Geraden" (s. Bild 4 im ersten Beitrag)
(2) Gesamtzahl der Geraden ist
(3) Jetzt müssen (alle) Gerade(n) darauf geprüft werden, ob sie bei ganzzahlige Werte liefern oder nicht. Eine Primzahl liegt vor, wenn alle Werte nicht ganzzahlig sind:
6 ist also keine Primzahl...

Bei haben wir ein ähnliches Bild, nur dass
Da dies die einzige zu analysierende Gerade ist, ist 7 eine Primzahl.

Um das zu berechnen, braucht man eigentlich keine Information, bis auf . Und viel Geduld...

Eine Gleichung, mit der sich alle Primzahlen finden liessen, wäre dann in dem speziellen Fall im Bereich von gültig und müsste alle zurück liefern, für die gilt: .

Empirisch ist dabei einfach zu finden, dass es sich um 5 und 7 handelt. Keine Ahnung, wie man die Gleichung lösen kann %)

Allgemein gesehen, besteht die Lösung für aus
einem Gleichungssystem mit Gleichungen
bei

Habe ich immer noch auf keine Gesetzmässigkeit hingewiesen?
m_OO_m Auf diesen Beitrag antworten »
wieder ein Progrämmel
wieder mit der Bitte, sich nicht über meinen Programmierstil auszulassen - es geht um das Berechnungsprinzip.

Ausgabe:
Definitionsbereich: {961...1023}
30 Perioden
Gleichung 1: (x - 4) mod 2 != 0
Gleichung 2: (x - 9) mod 3 != 0
Gleichung 4: (x - 25) mod 5 != 0
Gleichung 6: (x - 49) mod 7 != 0
Gleichung 10: (x - 121) mod 11 != 0
Gleichung 12: (x - 169) mod 13 != 0
Gleichung 16: (x - 289) mod 17 != 0
Gleichung 18: (x - 361) mod 19 != 0
Gleichung 22: (x - 529) mod 23 != 0
Gleichung 28: (x - 841) mod 29 != 0
Gleichung 30: (x - 961) mod 31 != 0
11 Gleichungen generiert, 19 verworfen.
967
971
977
983
991
997
1009
1013
1019
1021
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von m_OO_m
Übrigens, zum Erastothenes: wenn ich Wikipedia richtig verstanden habe, funktioniert das Verfahren nur für Bereiche 1 bis n. Denn wenn wir z.B. den Bereich 6 bis n betrachten, ist 6 nach Erastothenes eine Primzahl (denn welche Primzahlen davor enthalten waren, "weiss" ja keiner).

Aha. Und woher "weißt" du in deinem Verfahren

Zitat:
Original von m_OO_m
Ausgabe:
Definitionsbereich: {961...1023}
30 Perioden
Gleichung 1: (x - 4) mod 2 != 0
Gleichung 2: (x - 9) mod 3 != 0
Gleichung 4: (x - 25) mod 5 != 0
Gleichung 6: (x - 49) mod 7 != 0
Gleichung 10: (x - 121) mod 11 != 0
Gleichung 12: (x - 169) mod 13 != 0
Gleichung 16: (x - 289) mod 17 != 0
Gleichung 18: (x - 361) mod 19 != 0
Gleichung 22: (x - 529) mod 23 != 0
Gleichung 28: (x - 841) mod 29 != 0
Gleichung 30: (x - 961) mod 31 != 0

dass die Primzahlen just jene Zahlen 2,3,5,7,11,13,17,19,23,29,31 sind? Das Gegenargument zu Eratosthenes ist also nicht wirklich eins. Eine leichtfertig und kühne, aber falsche Extrapolation des Eratosthenes-Verfahrens für einen anderen Anwendungsfall entwertet nicht das Original-Verfahren. Augenzwinkern
m_OO_m Auf diesen Beitrag antworten »

das brauche ich auch nicht zwingend, das macht einfach das Gleichungssystem kompakter. Es funktioniert auch so:

30 Gleichungen generiert, 0 verworfen.
967
971
977
983
991
997
1009
1013
1019
1021
10 Primzahlen gefunden.

Das Eine ist die Gesetzmässigkeit - mit dieser Periodität - das Andere, wie man diese vereinfacht bzw. Computertauglich macht. Um die ursprüngliche Logik - komplett ohne Eratosthenes - wiederherzustellen, muss man lediglich Zeilen 38 bis 43 auskommentieren.
Mystic Auf diesen Beitrag antworten »

@m_OO_m

Ich habe für mich oft die Erfahrung gemacht, dass Leute, welche viel in ihrer eigenen "versponnenen" Gedankenwelt leben, sich oft schwer tun damit, sich auf die Gedanken Anderer einzulassen... unglücklich

Vielleicht ist das ja auch ein Vorurteil, hier wird es jedenfalls voll bestätigt: Ich hatte mir oben die Mühe gemacht, für das kleine Beispiel der Primzahlsuche im Bereich 5^2,5^2+1,...,6^2-1 das Sieb des Eratosthenes zu adaptieren und es deinem Verfahren gegenüberzustellen... Statt diese Adaption des Siebs des Eratosthenes genau zu überdenken, kommst du damit, dass bei diesen Verfahren auf jeden Fall eine Liste der Primzahlen bis n benötigt, was, wie man schon an diesem Beispiel sieht, purer Unsinn ist und zeigt, dass du weder das Sieb des Eratosthenes, noch deinen eigenen Algorithmus wirklich verstanden hast... Wie ja schon aus dem Kommentar von HAL 9000 hervorgeht (und du auch inzwischen bemerkt zu haben scheinst, wie ich da in der Vorschau lese!), entstehen ja auch in deinem Algorithmus automatisch die Primzahlmoduln, ohne dass du dich wirklich darum "kümmerst"... Genauso ist es auch beim Sieb des Eratosthenes, egal ob in der Originalform oder der von mir adaptierten Variante...

Edit: Hab gerade deinen letzten Kommentar genauer gelesen und nehme hiermit meinen Klammernsatz von oben zurück, wonach du irgendetwas durchschaut hast... unglücklich
m_OO_m Auf diesen Beitrag antworten »

OK, meine Blödheit haben wir schon mal festgestellt, das ist doch schon mal was.
Wir bleiben bei
Erastothenes fängt bei Teiler an und streicht alle Werte wie von Dir beschrieben, also danach etc., u.A. auch innerhalb von .
Dies bedeutet aber, dass Du mit bis gehen musst, damit ausgesiebt ist (die „weggestrichenen“ Werte kommen nicht mehr dran, klar)
Jetzt noch einmal zu der Ausgabe des Programms:
Vorgabe: 1000
Definitionsbereich: {961...1023}
30 Perioden

Gleichung 30: (x - 961) mod 31 != 0

Primzahlen >= 1000:
1009
1013
1019
1021
4 Primzahlen gefunden.

Hier ist der größte Teiler 31, also
Allein an diesem Beispiel: warum soll ich denn Erastothenes nicht verstanden oder kopiert haben?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von m_OO_m
Erastothenes fängt bei Teiler an und streicht alle Werte wie von Dir beschrieben, also danach etc., u.A. auch innerhalb von .
Dies bedeutet aber, dass Du mit bis gehen musst, damit ausgesiebt ist (die „weggestrichenen“ Werte kommen nicht mehr dran, klar)

Es ist doch wohl selbstverständlich, dass man bei einem auf dein Intervall modifizierten Eratosthenes nicht mit anfängt, sondern mit , wobei man Startindex gemäß bestimmt. Was den Aufwand beim Wegstreichen natürlich drastisch vermindert, gerade für große . Augenzwinkern
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von m_OO_m
OK, meine Blödheit haben wir schon mal festgestellt, das ist doch schon mal was.

Sorry, wenn das so rüberkam, gesagt oder auch nur gemeint habe ich das jedenfalls nicht... geschockt

Zitat:
Original von m_OO_m
Dies bedeutet aber, dass Du mit bis gehen musst, damit ausgesiebt ist (die „weggestrichenen“ Werte kommen nicht mehr dran, klar)

Ne, auch in meinem schon mehrfach zitierten Musterbeispiel gehe ich nur bis n=5 und nicht bis zu deiner Schranke... Warum? Weil zusammengesetzte Zahlen <(n+1)^2 immer einen Teiler haben müssen, der höchstens n ist, weshalb dieser dann jedenfalls entdeckt wird, wenn man nur bis n geht...

Zitat:
Original von m_OO_m
Allein an diesem Beispiel: warum soll ich denn Erastothenes nicht verstanden oder kopiert haben?

Das geht mehr aus unserer bisherigen Diskussion hervor, wo du an einer Stelle behauptet hast, man bräuchte für das adaptierte Sieb des Eratosthenes schon eine Primzahltabelle, bevor man überhaupt anfängt... Das ist klar falsch, wie auch aus meinem Musterbeispiel hervorgeht... Ich "weiss" z.B. nicht, dass 4 keine Primzahl ist, aber ich "merke" es daran, dass es zu dem Zeitpunkt, wo ich es behandeln möchte (also für deine 3.Gerade) schon gestrichen wurde... Zu keinem Zeitpunkt schaue ich also in einer Primzahltabelle nach... Das war dann auch bei dir so (außer nach der allerletzten Änderung des Programms, wenn ich das richtig verstanden habe)...
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Es ist doch wohl selbstverständlich, dass man bei einem auf dein Intervall modifizierten Eratosthenes nicht mit anfängt, sondern mit , wobei man Startindex gemäß bestimmt. Was den Aufwand beim Wegstreichen natürlich drastisch vermindert, gerade für große . Augenzwinkern

Ja, so ist es, obwohl ich das bislang auch nicht beachtet habe... unglücklich Manche Dinge in einem Algorithmus fallen einem eben erst auf, wenn man ein Programm dafür schreibt...
HAL 9000 Auf diesen Beitrag antworten »

Mir fällt da für das Intervall auch eher folgendes modifizierte Eratosthenes-Verfahren ein:

Alle zusammengesetzten Zahlen in haben einen Primteiler .


a) Im Fall führen wir gleich ein normales Eratosthenes-Verfahrens für durch, fertig.


b) Im Fall , besonders aber für , führen wir ein zweistufiges Verfahrens durch:

1.Normales Eratosthenes-Verfahrens für , man erhält die Menge der darin enthaltenen Primzahlen, nennen wir sie .

2.Modifiziertes Eratosthenes-Verfahrens für : Dazu nimmt man sich alle der Reihe nach vor, und streicht in alle Zahlen für heraus.


Je größer im Vergleich zu ist, desto weniger fällt der Aufwand für Schritt 1. ins Gewicht. In der Hinsicht ist das Verfahren für den speziellen Anwendungsfall mit dann "nur" vielleicht nicht die glücklichste Wahl. Aber nun wieder auch nicht so schlecht, als dass es sich vor dem obigen "Geradenverfahren" verstecken müsste. Augenzwinkern
m_OO_m Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Das geht mehr aus unserer bisherigen Diskussion hervor, wo du an einer Stelle behauptet hast, man bräuchte für das adaptierte Sieb des Eratosthenes schon eine Primzahltabelle, bevor man überhaupt anfängt... Das ist klar falsch, wie auch aus meinem Musterbeispiel hervorgeht... Ich "weiss" z.B. nicht, dass 4 keine Primzahl ist, aber ich "merke" es daran, dass es zu dem Zeitpunkt, wo ich es behandeln möchte (also für deine 3.Gerade) schon gestrichen wurde... Zu keinem Zeitpunkt schaue ich also in einer Primzahltabelle nach... Das war dann auch bei dir so (außer nach der allerletzten Änderung des Programms, wenn ich das richtig verstanden habe)...


Ich habe das eigentlich nicht behauptet. Es ging irgendwann darum, dass man grössere Perioden fallen lassen kann, solange sie das ganzzahlige Mehrfache kleinerer Perioden sind. Zwangsläufig bleiben dabei nur Gleichungen übrig, die auf Primzahlen basieren. Das wurde dann so verstanden, als ob ich eine Liste der Primzahlen benötigen würde, um weitere Primzahlen zu ermitteln.

Das Programm habe ich tatsächlich geändert, allerdings mehr vom "schauen, ob es passt" in "einen Startpunkt vorgeben und ab diesem Punkt Primzahlen ausgeben". Die Überlegung dahinter ist dieselbe. Der Durchsatz ist nur gestiegen - ich habe Ausgaben auf das Minimum reduziert:

Vorgabe: 10000000000000
Definitionsbereich: {9999995824729...10000002149283}
3162276 Perioden
227647 Gleichungen generiert, 2934629 verworfen.
Primzahlen >= 10000000000000:
10000000000037
10000000000051
10000000000099
...
10000000029869
1000 Primzahlen in 57386 ms. gefunden; 57 ms. pro Zahl
BUILD SUCCESSFUL (total time: 12 minutes 19 seconds)

er hat also 11 Minuten lang seine Gleichungen vorbereitet und 1 Minute lang gerechnet...
m_OO_m Auf diesen Beitrag antworten »

Zitat:
Original von m_OO_m
Allgemein gesehen, besteht die Lösung für aus
einem Gleichungssystem mit Gleichungen
bei


Eigentlich ging es mir nicht darum, ein Programm zu entwickeln, das schnell Primzahlen findet, sondern eine Art allgemeine Lösung für das Gleichungssystem zu finden. Dann könnte man die Primzahlen berechnen und nicht durch einen Bereich laufen und schauen, welche Zahlen in den Kram passen...
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von m_OO_m
er hat also 11 Minuten lang seine Gleichungen vorbereitet und 1 Minute lang gerechnet...

Naja, wirklich beeindruckend ist das noch immer nicht... In Maple muss man auf die Ausgabe von

(nextprime@@1000)(10^13);

was im wesentlichen die gleiche Rechnung ist, gerade mal 0.8s warten... Augenzwinkern

Edit: Rechenzeit nach oben korrigiert... Man beachte, dass bei dieser "quick and dirty"-Rechnung zwar nur die letzte Primzahl ausgegeben wird, aber doch alle tausend berechnet werden müssen...
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von m_OO_m
Definitionsbereich: {9999995824729...10000002149283}

[...]

1000 Primzahlen in 57386 ms. gefunden; 57 ms. pro Zahl

Ich hatte das bisher so aufgefasst, dass du ALLE Primzahlen in diesem Definitionsbereich suchst? Das sind deutlich mehr als 1000, eher so um die 200000 ... verwirrt

Da muss ich wohl was falsch verstanden haben.


EDIT: Es sind übrigens exakt 211473 Primzahlen in diesem Intervall zu finden (25 Sekunden Rechnung mit obigen Algorithmus). Augenzwinkern
HAL 9000 Auf diesen Beitrag antworten »
RE: ... das Progrämmel
Eine Anmerkung noch dazu:

Zitat:
Original von m_OO_m
Es verwendet außerdem keine Division, es beobachtet nur die "Zyklen" der unterschiedlichen Geraden - ist im Programm deutlich ersichtlich.

Was im Java-Quelltext deutlich ersichtlich ist: Zweimal im Programm, jeweils in den innersten Schleifen, wird eine Modulo-Operation % durchgeführt. Die dürfte sich vom Aufwand her nicht wesentlich von einer Division unterscheiden. Augenzwinkern
Mystic Auf diesen Beitrag antworten »
RE: ... das Progrämmel
Ja, ich habe auch mal einen kurzen Blick auf den Java.Quelltext geworfen und es gibt einiges, was ich nicht verstehe... Insbesondere scheint mir, als ob der der Autor - warum auch immer - anfänglich alles für die Klasse BigInteger durchziehen wollte, aber dann nicht konnte, d.h., er hat sich dann doch letzlich in wesentlichen Passagen des Programms wieder nur auf den Ganzzahltyp int beschränkt...

Unnötig kompliziert scheint mir auch die Routine sqrt zur Bestimmung des ganzzahligen Anteils einer Wurzel... Warum nicht einfacher so, wie in nachfolgender Maple-Version

code:
1:
2:
3:
4:
5:
6:
7:
floorsqrt:=proc(n::nonnegint)
    local x:=1;    
    do      
       x:=floor((x+n/x)/2);      
       if x^2<=n then return x end if    
   end do 
end:

d.h., auch mit dem Heron'schen Verfahren, aber eben viel geradliniger... verwirrt
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »