Primzahlen und das Sieb des Eratosthenes

Primzahlen haben mich irgendwie schon immer fasziniert. Selber sind sie nur durch sich selbst und durch 1 teilbar. Aber den theoretischen Teil kann Wikipedia eh besser.

Eine Primzahl ist eine natürliche Zahl, die größer als eins und ausschließlich durch sich selbst und durch eins teilbar ist. Eine Primzahl ist also eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler. Die kleinsten Primzahlen sind

Wikipedia – Primzahlen

Also habe ich mich dran gemacht ein Primzahlen Programm, das ich bereits mit meinem GTR und Basic realisiert habe in C# nach zubauen.

Nach einigen Problemen mit den Datentypen und das meine Berechnen viel zu lange gedauert haben, habe ich mich mit dem Thema „Threads“ beschäftigt, und bin trotz einer plumper Berechnungsmethode auf brauchbare Ergebnisse gekommen.

Die Berechnungsmethode in einem separaten thread:

for (i = 3; i < Math.Sqrt(prime); i = i + 2) 
//for schleife zur berechnung
//(er prüft die schleife von 3-wurzel(prime))
{
 percent = Math.Round((i * 100) / (Math.Sqrt(prime)), 2); 
  //Prozentangabe für den Fortschritts Balken
 if (prime / i == Math.Round(prime / i))
  //überprüfen ob prime durch i teilbar ist mit ganzzahligem ergebniss
 {
  rechnet = false; //er rechnet nichmehr
  sw.Stop(); //stoppe Zeit Messung
  time = toTime(sw.Elapsed.TotalSeconds); //vergangene Zeit ermitteln

  percent = 100;
  MessageBox.Show(prime + " ist nicht Prim weil "
    + prime + "/" + i + " = " + prime / i,
    "Ergebnis", MessageBoxButtons.OK, MessageBoxIcon.Exclamation);
  break; //schleife abbrechen
  }
}

Das Primzahlen Testen Programm gibt es hier: [download id=“6″ format=“1″]

Eine andere eventuell elegantere Möglichkeit wäre ein das Sieb des Eratosthenes zu verwenden. Hier wird für jede Zahl in einem frei wählbaren Maximalwert n ein Bool Datentyp in einem Array angelegt. Und dann werden entsprechend der Überlegung, dass eine zahl i alle Zahlen des Vielfachen der Zahl i ausschließt, die werte im Array auf Falsch also „keine Primzahl“ gesetzt. Dadurch werden manche Zahlen nicht ausgeschlossen, die nächste nicht ausgeschlossene Zahl ist eine Primzahl p. Allerdings schießt das vielfache der Primzahl p wiederum andere Zahlen aus.

Bsp: angefangen wird mit 2

2,3,4,5,6,7,8,9,10,11,12,13,14,15…
2,3,4,5,6,7,8,9,10,11,12,13,14,15… Primzahl Zwei: 3
2,3,4,5,6,7,8,9,10,11,12,13,14,15… Primzahl Drei: 5
usw…

Auf Wikipedia gibt es eine sehr schön animierte Grafik die das verständlicher macht.

Ein Gedanke zu “Primzahlen und das Sieb des Eratosthenes

  1. Abgesehen von den Rechtschreibefehlern im Post richtig klasse! Dem Code kann ich leider nicht ganz folgen, dafür ist mein Informatikkurs zu lange her…