AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Ein Algorithmus zur Primzahlenumeration

Ein Thema von Delphi-Laie · begonnen am 17. Jun 2012 · letzter Beitrag vom 24. Jun 2012
Antwort Antwort
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#1

Ein Algorithmus zur Primzahlenumeration

  Alt 17. Jun 2012, 17:09
Eine (einfache oder komplexere) Formel zur Erzeugung der Primzahlen, optimalerweise der x. Primzahl, soll es ja bis heute nicht geben. Wohl gibt es aber inzwischen von Gerald Bühler einen siebfreien (i.Ggs.z. Eratosthenes, Atkin) Algorithmus zur Generierung derselben, der allerdings mit einem Hiflsarray arbeitet und bei größeren Zahlen auch spürbar langsamer wird. Das geht aber vom algorithmischen Niveau her immer noch um Größenordnungen über die triviale und von der Laufzeit her inakzeptable Schulmethode heraus, über Probedivisionen aller ungeraden Zahlen (und ggf. Einbezug noch weiterer Teilbarkeitsregeln) bis hin zu den Wurzeln der Zahlen zu operieren und so die Primeigenschaft nach der Versuch-Und-Irrtum-Methode festzustellen.

Interessanterweise ist jener Algorithmus erweiterbar, wie ich hoffte, probierte und herausfand, sodaß man sich nicht vorher festlegen muß, bis zu welcher natürlichen Zahl n (oder alternativ bis zur Primzahl bis zur Nummer soundso) man enumerieren möchte (im Gegensatz zu den Sieben). Es sind also beliebig viele Primzahlen aufsteigend lückenlos generierbar bzw. enumerierbar.

Im Anhang befinden sich 3 Demonstrationsprogramme dazu, die ich auf die Schnelle erstellte. Primgen 1 ist das nach Delphi übersetzte Original, während Primgen 2 und 3 die nach oben offene Enumeration demonstrieren.
Angehängte Dateien
Dateityp: zip Primzahlenumeratoren.zip (473,3 KB, 22x aufgerufen)
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.474 Beiträge
 
Delphi 10.1 Berlin Starter
 
#2

AW: Ein Algorithmus zur Primzahlenumeration

  Alt 24. Jun 2012, 18:39
Zurecht wurde im Delphi-Forum (bzw. in der Entwickler-Ecke) kritisiert, daß der Speicherverbrauch dieses hier vorgestellten Algorithmus' einem Eratoshenes-Sieb, das nur ungerade Zahlen speichert, gleicht.

Ich nahm mich der Sache an. Schon in der ersten Version fiel mir auf, daß das Hilfsarray überwiegend (in der weit überwiegend höheren und damit größeren "Hälfte") aus Nullen besteht. Tatsächlich wird es an falscher Stelle des Algorithmus' falsch dimensioniert, konret: natürlich überdimensioniert. Jetzt müßte es stimmen. Ich lud bei den drei Demonstrationsprogrammen die jeweils verbesserte Version hier hoch. Die obere Version ist also obsolet, leider kann ich den Beitrag oben nicht mehr editieren und mithin das dort löschen bzw. erneuern.

Viele Grüße

Delphi-Laie

Edit 1: Noch eine kleine Unsauberkeit korrigiert.

Edit 2: Nach dieser Korrektur wächst die Länge des Hilfsarrays anscheinend nur noch logarithmisch mit der Anzahl der ermittelten Primzahlen, fällt also bei wachsender Primzahlmenge bwz. wachsendem Primzahlarray immer weniger bis kaum noch ins Gewicht.
Angehängte Dateien
Dateityp: zip Primzahlenumeratoren.zip (473,3 KB, 14x aufgerufen)

Geändert von Delphi-Laie (25. Jun 2012 um 09:45 Uhr)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 11:26 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf