C Lösungsansatz Primzahluntersuchung auf Primzahldrillinge

Hallo,
ich schreibe aktuell ein Programm welches Primzahlen im Bereich 2-2^16 untersucht.
Bis jetzt habe ich mir alle Primzahlen aufzählen lassen, die Anzahl gezählt und die Anzahl der Primzahlzwillinge untersucht.
Primzahlzwillinge sind zwei aufeinander folgende Primzahlen, deren Differenz 2 ist.

Jetzt möchte ich den Zahlenbereich noch auf Primzahldrillinge und -Vierlinge untersuchen und deren Anzahl ermitteln.
Primzahldrillinge existieren, wenn sich unter 4 aufeinander folgenden ungeraden zahlen 3 Primzahlen befinden.
Primzahlvierlinge existieren, wenn sich unter 5 aufeinander folgenden ungeraden zahlen 4 Primzahlen befinden.
Leider fehlt mir aber ein Ansatz wie die Überprüfung stattfinden kann.

Ich habe schon ein Array mit allen ungraden Zahlen von 3 - 2^16 erstellt.
Theoretisch müsste ich jetzt ja immer 4 aufeinanderfolgende Zahlen aus diesem Array kopieren und dann prüfen ob dort 3 Primzahlen drin sind. Wenn das der Fall ist, dann den Zähler um eins hochsetzen, und dann mit dem Prüfraster um eine Stelle weiter zu rücken. Aber wie kann ich das in Programmcode umsetzten? Leider fehlt mir dazu momentan ein Ansatz.
Von daher wäre ich über jede Hilfe dankbar.

Gruß
Torben

TRBN schrieb:

Ich habe schon ein Array mit allen ungraden Zahlen von 3 - 2^16 erstellt.
Theoretisch müsste ich jetzt ja immer 4 aufeinanderfolgende Zahlen aus diesem Array kopieren und dann prüfen ob dort 3 Primzahlen drin sind.

Zum Vergrößern anklicken....

Vermutlich gibt es da viel clevere Varianten aber spontan würde ich sagen: Du überprüfst ob eine ungerade Zahl prim ist und NUR DANN guckst du dir auch die 4 oder 5 folgenden Zahlen an und überprüfst die ebenfalls.


Edit: Oder wenn du schon die Primzahlzwillinge kennst musst du nur die Umgebung dieser Zwillinge überprüfen. Denn wenn unter 4 aufeinanderfolgenden ungeraden Zahlen 3 prim sein müssen ist da definitiv ein Primzahlzwilling dabei.

Warum nicht über das Primzahlen array laufen und wenn array-array[i+1]=2 dann Zwilling++

also so prüfe ich ob es sich um Zwilling handelt:

meine Primzahlen habe ich mithilfe des Siebs nach Eratosthenes berechnet:

Dieses Prinzip kann ich aber ja nicht anwenden, wenn ich nur 4er Paare aus der Reihe untersuche.
Die Reihe sieht ja wie folgt aus:
3|5|7|9|11|13|15|...
untersuche ich das erste viererpaar, dann funktioniert es noch: ich nehme die 3 und schaue welche Ziffern durch 3 Teilbar sind und streiche die--> die 9 fällt also weg. 3,5,7 sind 3 Primzahlen, also ist es ein Vierling.
Aber schon wenn ich einen Schritt weiter gehe, habe ich ein Problem:
|5|7|9|11| 9 ist keine Primzahl, lässt sich aber nicht durch 5, 7 oder 11 Teilen....

Also rein wegen der Übersicht würde ich nur auf eine laufvariable setzen und so wie in meinem Beispiel drauf zugreifen.
Und den else Zweig kannst du die auch sparen, da unabhängig der if Abfrage inkrementiert werden soll.

aber damit kann ich dann doch nur die Zwillinge zählen? Das bringt mir nichts für Drillinge . Oder habe ich gerade eine Denkblockade?

Ein Gedankengang:

(I) Wenn ich das richtig sehe, speicherst du ja die Primzahlen als Liste (primzahl[]) ab, wenn du das Sieb durchgehst. Diese Liste ist verhältnismäßig klein (also gegenüber 2^16).

(II) Definition:

Primzahldrillinge existieren, wenn sich unter 4 aufeinander folgenden ungeraden zahlen 3 Primzahlen befinden.

Zum Vergrößern anklicken....

(III) 4 aufeinanderfolgende, ungerade Zahlen (u):




(IV) Differenzen:

(a) (2k+3) - (2k-1) = 4 für alle k. # 2 direkte Nachfolger ohne Übersprung
(b) (2k+5) - (2k-1) = 6 für alle k. # 2 Nachfolger mit einer ungeraden Zahl übersprungen

# Beispiele
#
# 3, 5, 7 => 7 - 3 = 4. CHECK (a)
# 5, 7, 11 => 7 - 5 = 6. CHECK (b, 9 übersprungen)
# 7, 11, 13 => 13 - 7 = 6. CHECK (b, 9 übersprungen)
# 11, 13, 17 => 17 - 11 = 6. CHECK (b, 15 übersprungen).
# 13, 17, 19 => 19 - 13 = 6. CHECK (b, 15 übersprungen)
# usw...
​

(V) Bedingung(en): { primzahl[i+2] - primzahl == 4 } || { primzahl[i+3] - primzahl == 6 }

(VI) Ist (V) nicht erfüllt, umfasst die Spannweite mind. 5 aufeinanderfolgende, ungerade Zahlen zwischen primzahl[i+3] und primzahl. Ergo brauchst du nur genau (V) anzahl-2 mal überprüfen. Is ja vom Prinzip her nichts anderes, als wie du es in deinem ersten Code-Schnipsel auf Zeile 6 gemacht hast:

Code:

if (primzahlen[j] - primzahlen[i] == 2) {

Für Vierlinge musst du bei (V) nur die beiden Bedingungen anpassen:

(V*) Bedingung(en): { primzahl[i+3] - primzahl == 6 } || { primzahl[i+4] - primzahl == 8 }

Dürfte wohl klar sein, dass du nicht auf Vierlinge abfragen brauchst, wenn (V) nicht erfüllt wurde.

Ich denke, dass das dein Problem löst. Du hattest die Lösung ja eigentlich schon gehabt, hast es in der Fortführung nur verdreht. Willst du die Anzahl der n-Tupel zählen, musst du selbstverständlich für jedes Tupel einen eigenen Zähler verwenden.

---

Anmerkungen zum Code:

1) In Zeile 1 und Zeile 9: Warum bitte 'static'?
2) In Zeile 9: Warum auf einmal 'float'?
3) Vergleiche mal die Schleifen in Zeile 2 und Zeile 11: Kann man die zusammenfassen?
4) Zeile 9: Warum ist 'primzahlen[]' ein Array, der 65536 Elemente hat?

2) In Zeile 9: Warum auf einmal 'float'?

Zum Vergrößern anklicken....

Das hab ich mich bei Primzahlen auch gefragt X)

Text wegen Dummheit gelöscht, ich bleib hier lieber nur Leser...

Prinzipiell gibt es zwei einfache Lösungsansätze. Einen statischen, bei dem du vorher festlegst, wie groß die Zahl maximal sein darf:
1) Du filterst (z.B. mittels Sieb des Eratosthenes) auf alle Primzahlen
2) Du verschiebst ein Fenster anschließend über alle Primzahlen und prüfst, ob die Primzahlen im Fenster den gesuchten Kriterien entsprechen. Falls ja, erfolgt die notwendige Ausgabe (z.B. Zähler erhöhen)

Und es gibt einen dynamischen Ansatz, bei den du zum Programmierzeitpunkt keine Zahlen kennen musst (ist aber auch schwerer zu programmieren):
1) Du iterierst über alle Zahlen und nutzt einen Algorithmus (z.B. das Sieb des Erathostenes) um inkrementell zu bestimmen ob die aktuelle Zahl eine Primzahl ist. (Im Fall Sieb des Eratosthenes empfiehlt es sich hier alle Primzahlen zu speichern, damit man auch pro Zahl prüfen kann, ob es sich um eine Primzahl handelt. Ideal sind hier Zeigerstrukturen)
2) Findest du eine Primzahl, prüfst du, ob diese und ihre n Vorgänger die gesuchten Kriterien erfüllen.

Wie gesagt, Ansatz zwei ist erheblich schwerer umzusetzen.

Ein Fenster ist idR. ein kleiner Satz Variablen, indem du nur einen Ausschnitt einer Sequenz betrachtest. Verschiebst du dein Fenster auf dem Ausschnitt um eins, dann überschreibst du den ältesten Wert mit dem neuen - so hast du wieder ein aktuelles Fenster und dir entgeht nichts, weil du ja die gesamte Folge vergleichst.

Das sind jetzt zwei Ansätze, ohne konkreten Implementierungsvorschlag