Question

Wie findet man Primzahlen heraus?

Answer 1

die primitivste Methode ist der sog. Sieb des Eratosthenes:

Du schreibst alle Zahlen von 1,2,3,4... hin.

Dann streichst Du die 1 durch, weil die keine Prinzahl ist (das ändert sich alle paar Jahrzehnte, mal ist sie Primzahl, mal ist sie nicht, im Augenblick ist es es wieder einmal nicht).

Die nächste nicht durchgestrichene Zahl ist eine Primzahl (hier die 2). Nun streichst Du alle folgenden Vielfachen von 2 auch durch.

Die nächste nun nicht durchgestrichene Zahl ist eine Primzahl (hier die 3). Nun streichst Du alle folgenden Vielfachen von 3 auch durch.

Die nächste nun nicht durchgestrichene Zahl ist eine Primzahl (hier die 5; die 4 wurde bereits als Vielfaches von 2 gestrichen). Nun streichst Du alle folgenden Vielfachen von 5 auch durch.

Usw. usw.

Es gibt viele solcher "Siebe", die meist effizienter arbeiten und die Teilbarkeitsregeln der Zahlen besser ausnutzen. Problem aller Siebe ist jedoch, dass man immer von vorne beginnen muss.

Ein wichtiges Problem der Mathematik ist die Frage, ob eine gegebene, oft sehr große Zahl (z.B. 12983462147912549125349751239461280451792458012640182935641) eine Primzahl ist. Mit einem Sieb wären die Liste sehr lang und der Aufwand sehr groß, da gibt es andere Methoden.

Grundsätzlich würde ich Dir vorschlagen, Du nutzt eine (am besten mathematische) Bibliothek (einer Universität), oder wühlst Dich durch das Internet.

Grüße,

M.B.

Answer 2

Primzahlen haben genau zwei natürliche Teiler. Es gibt unterschiedliche Verfahren, wie dieser Umstand genutzt werden kann, um Primzahlen zu identifizieren. Es gibt auch noch andere Verfahren. Was genau möchtest du wissen und was ist der Hintergrund deiner Frage?

Comments

Hallo Gast az0815,

...es gibt unterschiedliche Verfahren... es gibt auch noch andere Verfahren... ( als unterschiedliche? ). Verstehe einer dieses Wortgeknuddel. Warum nicht gleich zwei Verfahren hinschreiben, Wäre auch für mich interessant.

---

Es gibt unterschiedliche Verfahren, die mögliche teiler untersuchen, sowie weitere verfahren, die ganz anders arbeiten.

Answer 3

Wenn du eine Zahl (> 10 ; denn für die ersten ist es ja eh klar  )untersuchen willst, um festzustellen, ob es eine Primzahl ist,

kannst du so vorgehen:

Du teilst die Zahl durch die ersten Primzahlen 2;3;5;7;11;13; etc.

und hörst auf, wenn du entweder einen Teiler gefunden hast

(dann ist es keine Primzahl) , oder die

Zahl kleiner ist, als das Quadrat der zuletzt untersuchten Primzahl.

Also etwa bei 137 prüfst du Teilbarkeit durch

2 (nix) 3(nix) 5(nix) 7(nix) 11(nix) 13(nix)

Dann ist 137 eine Primzahl, denn 13² > 137.

Comments

Braucht man bei 137 nicht eigentlich nur bis FLOOR(√137) = 11 zu prüfen?

D.h. eigentlich würde ich gar nicht mehr versuchen ob 13 ein Teiler ist, weil 13 dann doch kein Teiler sein kann.

---

\( 13 \) könnte im Prinzip schon ein Teiler sein, nur wäre wegen \( 137 : 13 < \sqrt{137} \) ein potentieller weiterer Teiler bereits gefunden.

---

Da ist was dran. Also reicht es hier bis 11.

---

Richtig. Aber wenn man bereits einen Teiler gefunden hätte, hätte man ja auch nicht mehr die 137 nach weiteren Teilern untersucht sondern eben 137 durch den gefundenen Teiler.

---

Im Prinzip kann \( 13 \) aber dann ein Teiler von \( 137 \) sein und wenn \( 13 \) ein Teiler von \( 137 \) ist, dann ist es übrigens auch ein Teiler von \( 137 : a \) mit \( a \leq 11 \).