[h4x9r1zeee]

Hallo allerseits.

Seit kurzem versuche ich mich an der Programmierung. Dabei bin ich auf eine Aufgabe gestoßen die einen Algorithmus fordert um erkennen zu können ob die eingegebene natürliche Zahl sich um eine Primzahl handelt.

Mein Ansatz:

1.Gebe die zu prüfende Zahl ein.
2. vergleiche die zu prüfende Zahl mit 1.
2.1 Wenn sie gleich sind gebe aus: "Die 1 ist keine Primzahl". Fahre mit Schritt eins fort.
3. Speichere die wurzel aus der zu prüfenden Zahl in tmax (/n=tmax)
4. Setze t=2
5. Vergleiche t mit tmax
5.1. Ist t größer als tmax dan gebe aus "De Zahl ist eine Primzahl". Fahre mit Schrit ein fort.
6. Ist t kleiner oder gleich tmax dann teile die zu prüfende Zahl durch t (n%t)
6.1. Wenn ein rest übrigleibt dann addiere auf t +1 (t=t+1) und Fahre mit Schritt 5 weiter fort.
7. Wenn kein Rest bleibt dan gebe aus die "Zahl ist keine Primzahl" Fahre mit Schritt eins weiter fort.

Was mir natürlich selber auffällt ist das bei größeren Zahlen viel gerechnet werden muss obwohl man mit Schritt 3 schon viel an Arbeit erspart bleibt. Dennoch bein einer zu prüfenden Zahl von z.B. 15889 müsste man nach der Methode immer noch ganze 126 Möglichkeiten überprüfen (/15889=126.05). Lösung : Man teilt die gesuchte Zahl nur durch Primzahlen bis 126 was eigentlich möglich ist aber mir irgendwie Schwer fällt es in die Schrittkette einzubinden.

Über Kommentare und weitere Denkansätze würde ich mich freuen .

[spartan-b292]

Die 1 ist keine Primzahl das wäre so das erste was mir gerade einfällt. Ansonsten ist dein Test relativ kompliziert. Siehe auch: [ Link nur für registrierte Mitglieder sichtbar. Bitte einloggen oder neu registrieren ]

EDIT: Nach dem du nochmal editiert hast. Das was du vorhast nennt sich Sieb des Eratosthenes oder Sieb von Atkin. Ist auch in dem Wikiartikel verlinkt.

[h4x9r1zeee]

Ich finde es eine Grauzone. Die eins ist sowohl durch sich selbst als auch durch 1 ohne rest teilbar.
Doch trotzdem hast du recht, da die 1 bei der Primfaktorzerlegung nicht angewendet werden kann.

[Your_Conscience]

Die 1 ist keine Grauzone, sondern laut Definition keine Primzahl, denn eine Primzahl hat genau 2 natürliche Teiler, die 1 hat nur einen.

@h4x9r1zeee
Das was du vorhast, lohnt sich nur, wenn du von 2 - X alle Primzahlen haben willst, nicht aber wenn du nur wissen willst, ob eine bestimmte Zahl eine Primzahl ist.
Hier musst du die Zahl einfach durch alle Zahlen von 2 bis Wurzel(Zahl) teilen.

[h4x9r1zeee]

Okay, habs editiert.

Nach etwas einlesen bin ich auf die Mersene Zahl gestoßen.

Nun dan würde der neue Algorithmus so aussehen:

1.Eingabe: Gesuchte Primzahl "n"
2. n=n+1
3.log n / log 2 = i
4.Vergleiche 2^i-1 mit n
4.1.Sind die Zahlen gleich gebe aus : Es ist eine Primzahl
4.2.Sind die Zahlen ungleich gebe aus: Es ist keine Primzahl
5.Ende

Doch kann man dem Lösungsweg 100% vertrauen ?

[Your_Conscience]

Wenn du eine Vermutung für einen Algorithmus hast, setz dich hin und programmieren ihn. Dann siehst du ja, ob er funktioniert oder nicht.

Deinem Lösungsweg kann man übrigens nicht vertrauen, denn es kommt unabhängig der Eingabe immer n-1 raus.
x^(log n / log x) - 1 ist immer n - 1.

Und versuche dich nicht gleich an den Mersenne-Zahlen, die sind im wahrsten Sinne noch etwas zu groß für dich.

[Kranklyboy]

Eine Möglichkeit, die vielleicht schneller geht, wäre die, dass man mithilfe des Siebs von Eratosthenes die Primzahlen bis zur Zahl n+1 generieren lässt und dann schaut ob die Zahl n im Sieb vorhanden ist.

[Your_Conscience]

Nein, du solltest vielleicht die ganzen Posts lesen bevor du etwas schreibst.

[h4x9r1zeee]

Ich danke dir Your Conscience das du mich darauf aufmerksam gemacht hast. Das gab mir wieder viel zudenken.
Auch in deinem ersten Punkt gebe ich dir vollkommen recht. Doch wie bereits weiter oben erwähnt steige ich mit dem Programmieren erst ein und wollte mir die grundlegenden Gedanken eines Algorithmus näher bringen (erst kommt doch die Theorie). Daraufhin hab ich mich angefangen etwas reinzusteigern obwohl ein ähnlicher- etwas einfacherer- Algorithmus als der erste den ich gepostet habe als Lösungsvorschlag der Aufgabe angegeben war.

Sollen doch die größeren Köpfe der Menschheit sich um einen genauen Primzahlentest den Kopf zerbrechen