Primzahlen: Programmbeispiele
Aus Wikibooks
Inhaltsverzeichnis |
[Bearbeiten] Sieb des Eratosthenes
Die Spezifikation des Algorithmus in Pseudocode ist in der Wikipedia zu finden.
[Bearbeiten] Haskell
Ein einfaches Primzahlsieb in der Programmiersprache Haskell implementiert. Der Speicherbedarf des Algorithmus ist in 
Bits, wobei p die Anzahl der auszugebenen Primzahlen und b die größte auszugebene Primzahl bezeichnet.
[Bearbeiten] Code
> module Sieve > where > sieb :: [Int] -> [Int] > sieb (l:ls) = l:sieb[x | x <- ls, mod x l /= 0] > take_primes n = take n $ sieb [2..]
Ausführen via
# hugs Sieve oder für eine schnellere Version # ghc -O2 --make Sieve.lhs # ghci Sieve
Im Haskell-Interpeter zur Ausgabe der beispielsweise ersten 100 Primzahlen:
Prelude Sieve> take_primes 100
[Bearbeiten] Gambas
Ein Programmbeispiel zur Primzahlberechnung findet sich im Wikibuch der Programmiersprache Gambas.
[Bearbeiten] Visual Basic 3
Siehe auch : Sieb des Erathostenes in Visual Basic programmiert
Dieses Programm liefert die Primzahlen von 1 bis 2100000000
Hinter dem Befehl Berechnen steht der unten folgende Code . Der Code wurde mit vielen Rem Kommentaren versehen. Sie können die rem Kommentare herauswerfen und wahrscheinlich auch die Variable j streichen. Versuchen Sie den Fehler bei der Print Ausgabe mit der Startzahl 1-5 zu eliminieren.
[Bearbeiten] Code
Sub Befehl1_Click () Cls j = 1 Rem Zähler j für die ungeraden Zahlen die keine Primzahlen sind Rem ist wahrscheinlich überflüssig m = text1.Text Rem holt sich aus dem Textfeld1 die erste Zahl zum Testen If m / 2 = Int(m / 2) Then m = m - 1 Rem Falls diese Zahl ohne Rest durch 2 teilbar ist, also eine gerade Zahl ist Rem geht das Programm noch eine Zahl rückwärts um eine ungerade Zahl zu bekommen If text1.Text = "" Then m = 6 Rem Falls keine Startzahl eingegeben wurde wird die Startzahl m = 6 vergeben. For m = m To m + 1000 Step 2 Rem Hauptschleife Rem Die nächsten 1000 ungeraden Zahlen in einer Schleife durchlaufen lassen Rem m ist die Variable für die ungeraden Zahlen f = 1 Rem f ist die Variable für die Faktorentestung, Rem m teilbar durch f oder nicht n = m Rem n = ist die Testzahl, bei der noch nicht klar ist ob sie eine Primzahl ist Do While f < Sqr(n) Rem solange der Teiler f kleiner als die Wurzel Rem aus der Testzahl n ist, muß getestet werden f = f + 2 Rem Teiler von f = 1 beginnend um jeweils 2 vermehren , 3,5,7,9 etc erster Test also mit f = 3 Do While n / f = Int(n / f) Rem Teiler f testen solange bis n / f ohne Rest teilbar Rem Print "m = "; m; " n = "; n; " f = "; f; "j = "; j Rem Wenn Sie bei der letzten Zeile das Rem herauswerfen , Rem erkennen Sie die Bedeutung der Variablen j = j + 1 Rem j ist ein Zähler für die ungeraden Zahlen die keine Primzahlen sind Rem j ist wahrscheinlich überflüssig n = Int(n / f) Rem Die Testzahl n verkleinern auf die Zahl n/f Loop Loop A$ = " 1" + Chr(13) + " 2" + Chr(13) + " 3" If m < 7 Then Print A$ Rem Chr(13) = Zeilenwechsel Rem Am Anfang zwischen 1 und 5 gibt es Probleme mit der Ausgabe Rem deswegen werden die ersten drei Zeilen ersetzt durch A$ If n = m Then b = b + 1: Print n: text1.Text = n Rem Wenn die Testzahl n nicht teilbar war durch f Rem ist es eine Primzahl und kann ausgedruckt werden If b = 30 Then m = m + 1000 Rem b ist die Zeilennummer, Rem bis Zeile b = 30 werden die berechneten Primzahlen ausgegeben Rem bei Zeile 30 wird die Schleife abgebrochen, Rem da m größer als m + 1000 gesetzt wird Rem wenn ihr Bildschirm die Zahlen nicht mehr komplett anzeigt Rem können Sie für b einen anderen Wert als 30 nehmen Next m Rem Hauptschleife durchlaufen , rem wieder Start am Beginn der Hauptschleife End Sub
[Bearbeiten] Java
Hier ein möglicher Quelltextes eines Java-Programm zur Ausgabe der Primzahlen von 1-100 (Der Bereich kann natürlich beliebig erweitert werden. Es ist dann nur darauf zu achten auch bei der 2. Schleife den Bereich zu erweitern) Die Primzahlen werden dann in der Console ausgegeben
[Bearbeiten] Code
public class primzahlen { public static void main(String[] args) { int zahl; // Zu überprüfende Zahl int zaehler; // Durch diese Zahl soll geteilt werden int teiler; // Anzahl der möglichen Teiler int zahl2; // Rest bei der Division for (zahl = 1; zahl <= 100; zahl++) // zahl <= x ist der zu überprüfende Zahlenraum { if (zahl == 1) // Ausschluss der Zahl 1 als Primzahl System.out.println(""); else { teiler = 0; for (zaehler = 1; zaehler <= 100; zaehler++) { zahl2 = zahl % zaehler; // Division der Ausgangszahl durch eine weitere und ablegen in der Variabel zahl2 if (zahl2 == 0) // Falls der Rest gleich 0 ist ist ein Teiler gefunden teiler++; } if (teiler == 2) // Wenn die Zahl genau 2 Teiler hat ist sie eine Primzahl System.out.println(zahl+" ist eine Primzahl, da sie genau "+teiler+" Teiler hat"); /*else // Andernfalls ist sie keine Primzahl System.out.println(zahl+" ist KEINE Primzahl");*/ } } } }
[Bearbeiten] C#
Folgende eigenständig lauffähige Konsolenanwendung (.NET 2.0) gibt alle Primzahlen bis n nach dem Sieb des Eratosthenes aus:
[Bearbeiten] Code
using System; using System.Collections.Generic; using System.Text; namespace eratosthenes { class Program { static void Main(string[] args) { int n = 100; bool[] primes = new bool[n]; for (int i = 2; i < n; i++) { primes[i]=true; } for (int i = 2; i < n; i++) { if (primes[i] == true) { for (int j = i * i; j < n; j=j+i) { primes[j] = false; } Console.WriteLine(i); } } Console.ReadLine(); } } }
[Bearbeiten] Delphi
Folgende Konsolenanwendung gibt mit Hilfe der Funkton isPrim() von einer bestimmten Zahlenmenge die Primzahlen aus.
[Bearbeiten] Code
program Primzahl; {$APPTYPE CONSOLE} uses SysUtils; function IsPrim(AInteger: Integer): boolean; var i: Integer; begin result := true; if (AInteger <= 1) then //Wenn Zahl kleiner ist als 2: keine Primzahl begin result := false; exit; //Funktion beenden end; for i := 2 to Round(Sqrt(AInteger)) do //Wenn eine Zahl n von 2 bis Wurzel(n) begin // nicht teilbar ist, ist sie eine Primzahl if AInteger mod i = 0 then //mod: Modulo = Rest begin result := false; exit; end; end; end; var a, b: Integer; i: Integer; begin Write('von: '); Readln(a); //a abfragen Write('bis: '); Readln(b); //b abfragen for i := a to b do if IsPrim (i) then Writeln(i); //wenn i eine Primzahl ist: i ausgeben Readln; end.
