Sieb-Algorithmus von Eratosthenes

Wie rufe ich R-Funktionen auf, wie selektiere ich Daten, ich weiß nicht genau ....

Moderatoren: EDi, jogo

Antworten
TopProtet
Beiträge: 7
Registriert: So Apr 18, 2021 12:36 pm

Sieb-Algorithmus von Eratosthenes

Beitrag von TopProtet »

Hey ich habe folgende Fragestellung und wäre über Hilfe sehr dankbar:) :

Schreiben Sie einen Code, der für eine gegebene Zahl n alle Primzahlen, die kleiner gleich n sind, bestimmt und in einem Vektor zusammenfasst.
Verwenden Sie daür den Sieb-Algorithmus von Eratosthenes, der wie folgt funktioniert:

1. Starten Sie mit einem Vektor, der die Zahlen von 2 bis n enthält und das aktuelle Sieb darstellt.

2. Iterieren Sie durch die Werte von 2 bis n:
• Überprüfen Sie, ob die Zahl im aktuellen Sieb enthalten ist.
• Ist die Zahl im aktuellen Sieb enthalten, dann entfernen Sie alle Vielfachen, aber nicht die Zahl selbst, aus dem aktuellen Sieb und erstellen Sie damit ein neues Sieb.

3. Diejenigen Zahlen, die am Ende im Sieb enthalten sind, stellen die Primzahlen dar.

Bestimmen Sie die Primzahlen und deren Anzahl für n = 300.

Danke im Voraus für jegliche Hilfe!
bigben
Beiträge: 2771
Registriert: Mi Okt 12, 2016 9:09 am

Re: Sieb-Algorithmus von Eratosthenes

Beitrag von bigben »

Hallo TopProtet,

die beste Hilfe, die ich Dir derzeit geben kann ist der Link auf diesen Thread: viewtopic.php?f=20&t=35
TopProtet hat geschrieben: So Apr 18, 2021 12:44 pm1. Starten Sie mit einem Vektor, der die Zahlen von 2 bis n enthält und das aktuelle Sieb darstellt.
Für Deine Aufgabe ist es sehr hilfreich, die Funktion seq zu kennen. Sie erzeugt beispielsweise Vektoren von 1 bis 5 oder von 20 bis 25. Probier mal folgendes aus:

Code: Alles auswählen

seq(from = 1, to = 5, by = 1)
seq(from = 20, to = 25, by = 1)
2. Iterieren Sie durch die Werte von 2 bis n:


Die Kombination der Befehle for und seq kann dabei sehr hilfreich sein.

LG,
Bernhard
---
Programmiere stets so, dass die Maxime Deines Programmierstils Grundlage allgemeiner Gesetzgebung sein könnte
jogo
Beiträge: 2085
Registriert: Fr Okt 07, 2016 8:25 am

Re: Sieb-Algorithmus von Eratosthenes

Beitrag von jogo »

Hallo TopProtet,

willkommen im Forum!
TopProtet hat geschrieben: So Apr 18, 2021 12:44 pm Hey ich habe folgende Fragestellung und wäre über Hilfe sehr dankbar:) :

Schreiben Sie einen Code, der für eine gegebene Zahl n alle Primzahlen, die kleiner gleich n sind, bestimmt und in einem Vektor zusammenfasst.
Verwenden Sie daür den Sieb-Algorithmus von Eratosthenes
vor etwa einem Jahr habe ich sowas programmiert. Damals ging es aber um das Finden von Primzahlzwillingen.
... , der wie folgt funktioniert:

1. Starten Sie mit einem Vektor, der die Zahlen von 2 bis n enthält und das aktuelle Sieb darstellt.
Das habe ich bei meinem Programm etwas anders angelegt. Vielleicht kannst Du es ja trotzdem als Anregung nutzen:

Code: Alles auswählen

n <- 500 
x <- logical(n)
x[-1] <- TRUE # 1 ist keine Primzahl
for (i in 2:sqrt(n)) {
  if (x[i]) x[seq(i+i, n, by=i)] <- FALSE
}
p <- which(x)
p
diff(p) == 2
p[which(diff(p) == 2)]
Gruß, Jörg
Antworten