Primzahlen: Sieb des Eratosthenes

Question

Aufgabe: Sieb des Eratosthenes Flussdiagramm erstellen.

Komme nicht weiter wie ich darstellen kann, dass ab eine bestimmte Grenzen nicht weiter gesucht werden muss. Ist es nicht Wurzel n? Ist der Flussdiagramm effizient?

Problem/Ansatz:

Comments

Dein Flussdiagramm fragt "i * j markiert?". Dabei läuft i*j bis n^2. Das macht keinen Sinn.

---

Ist es nicht einfacher, die Vielfachen aus der Liste zu entfernen, sodass die Primzahlen übrig bleiben?

---

Ist es nicht einfacher, die Vielfachen aus der Liste zu entfernen, sodass die Primzahlen übrig bleiben?

wenn man dies tut, bleiben nicht die Primzahlen übrig, sondern die sogenannten 'glücklichen Zahlen'.

Answer 1

Wenn die Zahl n keinen der Teiler von 2 bis k hat, dann sind auch \( \frac{n}{2} \) bis \( \frac{n}{k} \) keine Teiler von n.

Answer 2

Komme nicht weiter wie ich darstellen kann, dass ab eine bestimmte Grenzen nicht weiter gesucht werden muss. Ist es nicht Wurzel n?

Du kannst aufhören, wenn das Quadrat des Teilers (nicht der Index) mit dem gesiebt wird, größer ist als \(n\). Ist z.B. \(n=100\), so ist der letzte Teiler \(=7\), da \(11^2 \gt 100\) ist.

Ist der Flussdiagramm effizient?

Ein Flussdiagramm ist höchst ineffizient. Es hat den Charme des letzten Jahrhunderts ;-). Du meinst aber den Algorithmus, den Du darzustellen versuchst.

Es sollte nur mit Teilern gesiebt werden, die selber nicht markiert sind. Ist \(n=100\) reicht es aus, mit den Teilern \(2,\,3,\,5\) und \(7\) zu arbeiten. Es reicht als nicht, den Teiler einfach zu inkrementieren (bei Dir ++i), sondern solange zu inkremtieren, bis er auf eine unmarkierte Zahl trifft.

Und es ist höchst ineffizient zu fragen, ob i*j markiert ist, um anschließend i*j zu markieren, falls es nicht markiert war. Markiere es einfach, es spielt keine Rolle, ob es vorher schon markiert war.