Hallo 
Gibt es einen einfachen Algorythmus, mit dem ich feststellen kann ob eine Zahl prim ist?
Oder evtl. eine praktische Tabelle mit allen Prinzahlen bis, sagen wir mal, 10.000?
Und gehe ich richtig in der Annahme, daß es reicht, wenn ich eine Zahl a daraufhin untersuchen will, ob sie prim ist, wenn ich überprüfe ob sie durch eine Primzahl kleiner oder gleich der Wurzel von a teilbar ist?
Schönen Dank schonmal!
Gruß,
Trurl der Konstrukteur
Hallo!
Gibt es einen einfachen Algorythmus, mit
dem ich feststellen kann ob eine Zahl
prim ist?
Ja, solange die Zahlen nicht sehr groß sind (größer als ca. 1 000 000 - ab dann wird die Rechenzeit spürbar bis kritisch bis nicht akzeptabel).
Und gehe ich richtig in der Annahme, daß
es reicht, wenn ich eine Zahl a daraufhin
untersuchen will, ob sie prim ist, wenn
ich überprüfe ob sie durch eine Primzahl
kleiner oder gleich der Wurzel von a
teilbar ist?
Du mußt die Prüfung für alle Primzahlen, die kleiner oder gleich sqr(a) sind, durchführen (was Du wohl auch gemeint hast, denke ich).
Der in der folgenden Funktion implementierte Algorithmus tut genau dies:
FUNCTION ZahlIstPrim (n: INTEGER): BOOLEAN;
VAR i : INTEGER;
zip: BOOLEAN;
begin
ZahlIstPrim := FALSE;
IF (n MOD 2)=1 THEN
begin
zip := TRUE;
i := 3;
WHILE (i
Gruß
Martin
2 ist auch eine Primzahl (nt)
!
Hallo,
der Code in meinem ersten Posting ist leider nicht ganz OK: Die Funktion liefert für n=2 „FALSE“ zurück, obwohl 2 ja eine Primzahl ist, wie dirk-m81 - danke, Dirk - richtig bemerkt hat. Ja, ich weiß, das Verletzen der Sorgfaltspflicht beim Code-Testen wird mit Kommentare-Schreiben nicht unter drei Stunden bestraft… Ich bitte um Entschuldigung.
Hier die berichtigte Funktion:
FUNCTION ZahlIstPrim (n: INTEGER): BOOLEAN;
VAR i : INTEGER;
zip: BOOLEAN;
begin
(\* Für Null, Eins und alle negativen \*)
(\* Zahlen wird "FALSE" zurückgegeben \*)
IF n
Gruß
Martin
Hier die berichtigte Funktion:
FUNCTION ZahlIstPrim (n: INTEGER):
BOOLEAN;VAR i : INTEGER;
zip: BOOLEAN;begin
[…]
Vielen Dank, daß du dir soviel Mühe gemacht hast!
Ist das Turbo Pascal? … ich hab mich mit dem Programmieren noch nicht wirklich beschäftigt.
Gibt es auch einen Algorithmus, den man mit Papier und Bleistift durchführen kann?
Ich werd deine Funktion aber auf jeden Fall mal umsetzen… irgendwo hab ich Pascal noch rumliegen. (Wenn das Pascal ist… ich glaube aber schon)
Gruß,
Trurl der Konstrukteur
Ist das Turbo Pascal? …
ja, es ist Pascal
Gibt es auch einen Algorithmus, den man
mit Papier und Bleistift durchführen
kann?
noe - gibt keinen Algorithmus ausser rechnen
wenn du uebrigens alle Prinzahlen bis 10.000 suchst, geht das am einfachsten mit dem „sieb des Erastothenes“ - ein ziemlich trivialer Algorithmus - z.B. beschrieben unter http://www.cenbells.de/001.htm
Gruss
Dirk
Algorithmus auf Papier
Gibt es auch einen Algorithmus, den man
mit Papier und Bleistift durchführen
kann?
Ja und zwar das bereits angesprochenes Sieb des Erasthothenes (wo die THs in seinem Namen hinkommen und wo nicht, hab ich vergessen).
Schreib die natürlichen Zahlen von eins bis … (alle, die Du testen willst und ohne Lücken!) auf, am Besten in rechteckiger Anordnung - immer zehn Zahlen nebeneinander. Anschließend streichst Du erst einmal die Eins durch.
Von nun an mußt Du nur noch im Wechsel zwei Regeln befolgen:
die nächste freie Zahl ist eine Primzahl. Mach einen Kringel drum!
2.
streiche alle Vielfachen der gerade eingekringelten Zahl durch.
Nach der Streichaktion in 2. ist die nächste freie Zahl wieder eine Primzahl und Du kannst wieder streichen und so weiter. Am Anfang hast Du noch eine Menge zu tun, aber schon nach wenigen gefundenen Primzahlen werden die Streichungen weniger, weil es weniger Vielfache gibt und außerdem schon viele Zahlen gestrichen wurden.
Ach ja - der „Algorithmus“ endet, wenn eine gefundene Primzahl größer als die Quadratwurzel der größten Zahl ist, die Du aufgeschrieben hast.
Gruß
W.