Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Sieb des Eratosthenes

Anmerkung: Das Sieb des Eratosthenes gilt als der älteste bekannte Algorithmus. Siehe dazu auch den Artikel in der Wikipedia
 

Suchen der Primzahlen per Hand bis 30

Anmerkung: Man ist fertig mit dem "Sieben", wenn die aktuelle Primzahl größer ist als die Wurzel der oberen Grenze. Hier in diesem Beispiel: die obere Grenze ist 30, die Wurzel daraus 5,477225575051661  -  also braucht man für die 7 nicht mehr weiterarbeiten  =>  man kann aufhören (Abbruch).
 

Programm für die Primzahlen bis 100

use strict;
use warnings;

################### globale Variablen ########################

my ($primzahl, $vielfaches, $i);
my @feld = ();


################### Hauptprogramm ############################

&erstelle_feld();
&erste_primzahl();
while ($primzahl < 10) {
  &streiche_vielfache();
  &suche_naechste_primzahl();
}
&primzahlen_ausgeben();


################### Subroutinen ##############################

sub erstelle_feld {
  # wir erzeugen ein Feld von 1 bis 100
  for ($i = 0; $i < 100; $i++) {
    $feld[$i] = $i;
  }
}

sub erste_primzahl {
  # die erste Primzahl ist die 2
  $primzahl = 2;
}

sub streiche_vielfache {
  # erstes Vielfaches ist 2 * Primzahl
  $vielfaches = 2 * $primzahl;
  #  die Vielfachen der Primzahl werden 0 gesetzt (= gestrichen)
  while ($vielfaches < 100) {
    $feld[$vielfaches] = 0;
        $vielfaches = $vielfaches + $primzahl;
  }
}

sub suche_naechste_primzahl {
  # Primzahl um 1 vergrößern
  $primzahl++;               # $primzahl = $primzahl + 1;
  while ($feld[$primzahl] == 0) {
    $primzahl++;
  }
}

sub primzahlen_ausgeben {
  for ($i = 2; $i < 100; $i++) {
    if ($feld[$i] != 0) {
          print $feld[$i], ' ';  # statt $feld[$i] könnte auch $i genommen werden
        }
  }
  print "\n";
}

__END__

Das sah dann bei mir so aus:

Aufgaben

1. Bringen Sie das Programm zum Laufen
2. Um Primzahlen z.B. in einem größeren Bereich zu bestimmen, müßte die "100" in diesem Programm an 3 Stellen geändert werden. Verwenden Sie eine Variable $grenze.
3. Damit die "10" in der 3. Zeile des Hauptprogramms nicht mehr angepasst werden muss, ersetzen Sie diese durch  int(sqrt($grenze))+1 .
4. Testen Sie das Programm für verschiedene Bereiche. (Hier ist sicherlich $grenze = 30 sinnvoll, denn die Ergebnisse stehen ja oben zur Verfügung!)
5. Ergänzen Sie das Programm um eine Überschrift. Die soll unterstrichen werden, danach soll eine Leerzeile kommen.
6. Unter der Ausgabe der Primzahlen soll die Anzahl der gefundenen Primzahlen angegeben werden.
7. Für größere Bereiche soll wegen der Übersichtlichkeit in jeder Zeile 10 Primzahlen ausgegeben werden. (In der letzten Zeile die restlichen Primzahlen.)
8. Es soll die Anzahl der Primzahlzwillinge ermittelt werden, also die Anzahl solcher Paare wie 3 - 5, 5 - 7, 11 - 13, 17 - 19.
9. Auch die Primzahlzwillinge sollen ausgegeben werden (hier fordere ich kein bestimmtes Format, allerdings muss die Lösung erkennbar sein).

Für  $grenze = 500  sah das bei mir so aus:

zurück