Sieb des Eratosthenes + Pseudocode. 4 Aufgaben bitte hilfe

Question

Das „Sieb des Eratosthenes“ ist ein von dem griechischen Philosophen Eratosthenes (276-195 v. Chr.) entwickelter Algorithmus zur Berechnung aller Primzahlen bis zu einer vorgegebenen natürlichen Zahl n. Der Algorithmus in Umgangssprache (angelehnt an den „Duden der Informatik“):

1. Man schreibe alle Zahlen von 1 bis n hin und streiche die Zahl 1 durch.

2. Sei i die kleinste noch nicht durchgestrichene und nicht eingerahmte Zahl. Solange i existiert und i² ≤ n ist, rahme man i ein und streiche alle Vielfachen von i durch (die Vielfachen von i werden „ausgesiebt“).

3. Die eingerahmten und die nicht durchgestrichenen Zahlen sind die Primzahlen von 1 bis n.

 1 a) Führen Sie den Algorithmus zunächst auf einem Blatt Papier für die Zahlen von 1 bis 25 durch.

Mein Ansatz:

alle Zahlen von 1 bis 25 hingeschrieben und die 1 durchgestrichen. Solange i existiert und i² ≤ n ist rahme man i ein.

ich hab das so verstanden, dass die Quadratzahl kleiner gleich 25 sein soll. diese soll man einrahmen.

Die Zahlen sind 2, 3, 4, 5.

Das mit dem vielfachen versteher ich nicht ganz und die anderen aufgaben kann ich auch nicht

Bitte um Hilfeee!

 b) Welche Grundoperationen (elementare Algorithmen) lassen sich in obigem Algorithmus identifizieren?

 c) Auf jeder Stufe des Algorithmenentwurfs sollte man sich Gedanken zur Optimierung machen. Wie lässt sich der Algorithmus bereits jetzt optimieren, noch bevor er als Pseudocode ausformuliert wird? Welche Datenstruktur kann für das Sieb benutzt werden?

 d) Formulieren Sie den Algorithmus in Form von Pseudocode. Verwenden Sie dazu die Grundoperationen aus Aufgabe b)

Comments

Ich habe zum Sieb des Eratosthenes mal ein Video gemacht:

Da sollten die Fragen soweit geklärt sein. Fall nicht, bitte nachfragen.

---

omg Ehrenmann Vielen lieben Dank. <3 <3 <3 <3

ich habe jetzt Aufgabe a) verstanden Dankee :D

Aber die anderen Frage weiß ich nicht genau wie ich das beantworten soll.

Das Problem ist wir hatten beim Programmieren kein in range oder list (range) oder primazahlen.append und sowas nicht. Im Video Minute: der Code bei Minute 4:40)

ich bin generell schlecht im Programmieren :(

b) Welche Grundoperationen (elementare Algorithmen) lassen sich in obigem Algorithmus identifizieren?

Meine Idee:

Multiplikation, weil man ja zum Beispiel die Primzahl 2 mit 3 multipliziert  oder 3*4 = 12 rechnet und diese dann durchstreicht. Also das vielfache.

 c) Auf jeder Stufe des Algorithmenentwurfs sollte man sich Gedanken zur Optimierung machen. Wie lässt sich der Algorithmus bereits jetzt optimieren, noch bevor er als Pseudocode ausformuliert wird? Welche Datenstruktur kann für das Sieb benutzt werden?

 d) Formulieren Sie den Algorithmus in Form von Pseudocode. Verwenden Sie dazu die Grundoperationen aus Aufgabe b)

Answer 1

Aloha :)

Ich habe das Programm für dich in der Programmiersprache GO geschrieben. Du kannst es gerne kopieren und hier ausprobieren:

https://play.golang.org/

package main
import "fmt"

func main() {
    const n= 1000
    var a [n+1]int
    for i:=2; i<=n; i++ {
        a[i]=i
    }
    for i:=2; i<=n; i++ {
        for j:=2*i; j<=n; j+=i {
            a[j]= 0
        }
        if (i*i>n) {
            break //Optimierung
        }
    }    
    for i:=2; i<=n; i++ {
        if (a[i]>0) {
            fmt.Println(a[i])
        }
    }
}

Comments

wir haben JAVA aber danke ich versuch es gleich mal :D

---

Ich nehme gerne GO, weil ich damit eine sehr effiziente Sprache mit einer rieseigen Bibliothek habe. In Java muss man immer so viel Code scheiben, der eigentlich nichts tut (Klassenstrukturen, Getter, Setter, Entwurfsmuster, ...).

Du solltest das GO-Programm aber gut nach Java transformieren können, musst halt noch den Verwaltungscode drumherum schreiben ;)