# ============================================================================== # Primzahlberechnung # ------------------ # Stand: 09.05.2026 # ============================================================================== import datetime uppLim=1000000000 rest15={1, 5} print("Primzahlen im Bereich von 1 bis", uppLim) # ------------------------------------------------------------------------------ # 1 Ausschlussliste erstellen # ------------------------------------------------------------------------------ # Bem.: Da die Kandidatinnenliste keine Vielfachen von 5, 7, 11, 13, 17, 19, 23 # und 29 enthalten wird, reduziert sich die Größe der Ausschlussliste. # ------------------------------------------------------------------------------ zeitStempel_1=datetime.datetime.now() ab=[] aMax=uppLim/3 i=5 while i <= uppLim/6: p=6*i+1 if p*31 > uppLim: break j=5 while j <= i: q=6*j+1 pq=p*q if pq % 6 in rest15 and (pq % 5 != 0 and pq % 7 != 0 \ and pq % 11 != 0 and pq % 13 != 0 \ and pq % 17 != 0 and pq % 19 != 0 \ and pq % 23 != 0 and pq % 29 != 0 \ and pq <= uppLim): ab.append(pq) if pq > uppLim: break j+=1 i+=1 i=5 while i <= uppLim/6: p=6*i+1 if p*31 > uppLim: break j=5 while j <= uppLim/6: q=6*j+5 pq=p*q if pq % 6 in rest15 and (pq % 5 != 0 and pq % 7 != 0 \ and pq % 11 != 0 and pq % 13 != 0 \ and pq % 17 != 0 and pq % 19 != 0 \ and pq % 23 != 0 and pq % 29 != 0 \ and pq <= uppLim): ab.append(pq) if pq > uppLim: break j+=1 i+=1 i=5 while i <= uppLim/6: p=6*i+5 if p*31 > uppLim: break j=5 while j <= i: q=6*j+5 pq=p*q if pq % 6 in rest15 and (pq % 5 != 0 and pq % 7 != 0 \ and pq % 11 != 0 and pq % 13 != 0 \ and pq % 17 != 0 and pq % 19 != 0 \ and pq % 23 != 0 and pq % 29 != 0 \ and pq <= uppLim): ab.append(pq) if pq > uppLim: break j+=1 i+=1 print("Länge Ausschlussliste lang:", len(ab)) abSet=set(ab) ab=list(abSet) del abSet print("Länge Ausschlussliste kurz:", len(ab)) zeitStempel_2=datetime.datetime.now() print("Start Ausschlussliste: ", zeitStempel_1, " Ende Ausschlussliste: ", zeitStempel_2, " Dauer Step 1: ", zeitStempel_2-zeitStempel_1) # ------------------------------------------------------------------------------ # 2 Kandidatinnenliste # ------------------------------------------------------------------------------ # 2.1 Kandidatinnenliste initialisieren # ------------------------------------------------------------------------------ primeCands=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29] # ------------------------------------------------------------------------------ # 2.2 Kandidatinnenliste füllen # ------------------------------------------------------------------------------ # Dabei werden Vielfache von 5 und 7 ausgeschlossen. # ------------------------------------------------------------------------------ i = 5 while 6*i < uppLim: fakVor =6*i+1 fakNach=6*i+5 if fakVor % 5 != 0 and fakVor % 7 != 0 and fakVor % 11 != 0 and fakVor % 13 != 0 \ and \ fakVor % 17 != 0 and fakVor % 19 != 0 and fakVor % 23 != 0 and fakVor % 29 != 0: primeCands.append(fakVor) if fakNach % 5 != 0 and fakNach % 7 != 0 and fakNach % 11 != 0 and fakNach % 13 != 0 \ and \ fakNach % 17 != 0 and fakNach % 19 != 0 and fakNach % 23 != 0 and fakNach % 29 != 0: primeCands.append(fakNach) i+=1 zeitStempel_3=datetime.datetime.now() print("Länge Kandidatinnenliste: ", len(primeCands)) print("Start Kandidatinnenliste: ", zeitStempel_2, " Ende Kandidatinnenliste", zeitStempel_3, " Dauer Step 2: ", zeitStempel_3-zeitStempel_2) # ------------------------------------------------------------------------------ # 3 Ergebnisliste erstellen # ------------------------------------------------------------------------------ # 3.1 Kandidatinnenliste duplizieren # ------------------------------------------------------------------------ # Bem.: Als vorläufige Ergebnisliste. Sortierung nur für Kontrollzwecke. # ------------------------------------------------------------------------------ result=primeCands # ------------------------------------------------------------------------------ # 3.2 Vorläufige Ergebnisliste reduzieren # ------------------------------------------------------------------------------ # Bem.: Dazu werden zunächst diejenigen Einträge durch 0 markiert, die auch in # der Ausschlussliste enthalten sind. # ------------------------------------------------------------------------------ result=list(set(result)-set(ab)) del ab zeitStempel_4=datetime.datetime.now() print("Start Ergebnisliste: ", zeitStempel_3, " Ende Ergebnisliste: ", zeitStempel_4, " Dauer Step 3.2:", zeitStempel_4-zeitStempel_3) # ------------------------------------------------------------------------------ # 3.3 Ergebnisliste sortieren # ------------------------------------------------------------------------------ result.sort() zeitStempel_5=datetime.datetime.now() print("Start Sortierung: ", zeitStempel_4, " Ende Sortierung: ", zeitStempel_5, " Dauer Step 3.3:", zeitStempel_5-zeitStempel_4) print("Länge Ausgabeliste: ", len(result)) # ------------------------------------------------------------------------------ # 4 Ergebnisausgabe in Datei # ------------------------------------------------------------------------------ # Bitte das Ausgabeverzeichnis an eigene Umgebung anpassen: ausgabeDatei=open('f:\\\\02-Projekte\\10-Programmierung\\03-PythonTestprogramme\\PrimzahlenListe-2026-05-09.txt', 'w') for p in result: ausgabeDatei.write(str(p)+',\n') ausgabeDatei.close() del result zeitStempel_6=datetime.datetime.now() print("Start Ausgabe: ", zeitStempel_5, " Ende Ausgabe: ", zeitStempel_6, " Dauer Step 4: ", zeitStempel_6-zeitStempel_5) print("Start Gesamtlauf: ", zeitStempel_1, " Ende Gesamtlauf: ", zeitStempel_6, " Dauer gesamt: ", zeitStempel_6-zeitStempel_1) # Primzahlen im Bereich von 1 bis 100.000.000 # Länge Ausschlussliste lang: 14925267 # Länge Ausschlussliste kurz: 10033273 # Start Ausschlussliste: 2026-05-09 16:16:23.991620 Ende Ausschlussliste: 2026-05-09 16:17:03.046491 Dauer Step 1: 0:00:39.054871 # Länge Kandidatinnenliste: 15794728 # Start Kandidatinnenliste: 2026-05-09 16:17:03.046491 Ende Kandidatinnenliste 2026-05-09 16:17:17.022599 Dauer Step 2: 0:00:13.976108 # Start Ergebnisliste: 2026-05-09 16:17:17.022599 Ende Ergebnisliste: 2026-05-09 16:17:21.037409 Dauer Step 3.2: 0:00:04.014810 # Start Sortierung: 2026-05-09 16:17:21.037409 Ende Sortierung: 2026-05-09 16:17:21.513507 Dauer Step 3.3: 0:00:00.476098 # Länge Ausgabeliste: 5761455 # Start Ausgabe: 2026-05-09 16:17:21.513507 Ende Ausgabe: 2026-05-09 16:17:27.485002 Dauer Step 4: 0:00:05.971495 # Start Gesamtlauf: 2026-05-09 16:16:23.991620 Ende Gesamtlauf: 2026-05-09 16:17:27.485002 Dauer gesamt: 0:01:03.493382 # Primzahlen im Bereich von 1 bis 1.000.000.000 # Länge Ausschlussliste lang: 177970006 # Länge Ausschlussliste kurz: 107099701 # Start Ausschlussliste: 2026-05-09 17:55:56.020172 Ende Ausschlussliste: 2026-05-09 18:07:39.685246 Dauer Step 1: 0:11:43.665074 # Länge Kandidatinnenliste: 157947235 # Start Kandidatinnenliste: 2026-05-09 18:07:39.685246 Ende Kandidatinnenliste 2026-05-09 18:10:05.551528 Dauer Step 2: 0:02:25.866282 # Start Ergebnisliste: 2026-05-09 18:10:05.551528 Ende Ergebnisliste: 2026-05-09 18:22:22.104390 Dauer Step 3.2: 0:12:16.552862 # Start Sortierung: 2026-05-09 18:22:22.104390 Ende Sortierung: 2026-05-09 18:23:15.598780 Dauer Step 3.3: 0:00:53.494390 # Länge Ausgabeliste: 50847534 # Start Ausgabe: 2026-05-09 18:23:15.598780 Ende Ausgabe: 2026-05-09 18:24:42.048450 Dauer Step 4: 0:01:26.449670 # Start Gesamtlauf: 2026-05-09 17:55:56.020172 Ende Gesamtlauf: 2026-05-09 18:24:42.048450 Dauer gesamt: 0:28:46.028278