AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Primzahl-Check: Javascript > Delphi

Primzahl-Check: Javascript > Delphi

Ein Thema von zecke · begonnen am 7. Sep 2005 · letzter Beitrag vom 24. Mär 2006
 
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#33

Re: Primzahl-Check: Javascript > Delphi

  Alt 24. Mär 2006, 13:57
Zitat:
So ähnlich läuft es ab (kann mich in den Details aber irren).
Du irrst nicht, wobei es denoch eine faszinierende Umschreibung ist

Einfacher gesagt: die Mathemtik die in den verschiednenen Algos. benutzt wird ist eine andere.

Die einfachste Methode ist eine Trial Division mit allen ungeraden Zahlen (und 2) von 2 beginnend bis Wurzel(N). Das Laufzeitverhalten ist das schlechteste aller verfahren und es wächst Quadratisch.

Ein leichte Abwandlung dieses Tests ist mit 6n+-1 zu arbeiten. Das reduziert die Komplexität nur um einen konstanten Faktor, verändert aber nicht deren Progression.

Eine noch bessere Abwandlung benutzt bei dieser Trialdivision nur Primzahlen bis Wurzel(N).

In meinen Algos. verwende ich eine ganz andere Sichtweise:

1.) des mathematiche Verfahren ist im Grunde nicht exakt. D.h. es kann nur 100% exakt erkennen ob eine Zahl X KEINE Primzahl ist, aber wenn es sagt es IST eine Primzahl dann muß dies leider nicht stimmen.

2.) Punkt 1.) wird aber irrelevant weil Andere Leute schon zumindestens alle Zahlen bis 2^32 mit diesem Verfahren überprüft haben und die Parameter für diesen Test verifiziert haben. D.h. mein Verfahren enthält schon unsichtbares Wissen und Informationen. Das wäre so als wenn man extern einmalig mit einem sehr langsammen Test eine tabelle aller Primzahlen erzeugen würde und dann in dere eigenen Anwndung nur noch diese Tabelle implementiert und die zu testende zahl darin nachschlägt.

3.) mein Test besteht im Grunde aus 2 einzelnen und ganz verschiedenen Tests. Als erstes wird eine Testdivision zu allen kleinen Primzahlen bis 137 druchgeführt, und erst danach als zweiter Test der SPP Test.

Wichtig ist aber im Resulat nur die Laufzeit des Verfahrens. Mein Test ist egal mit welcher zahl man arbeitet von der Komplexität her annähernd linear, ist also unabhängig vom Kandidaten den man testen möchte immer gleich schnell.

"Mein Test" ist aber eigentlich nicht von mir, sondern von Mathematikern. Das einzigste was ich geleistet habe ist das ich deren mathematische Grundlagen in ein effizientes Stück Source umgewandelt habe.

Gruß Hagen
  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 21:15 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz