Primzahlen: Programmbeispiele

Aus Wikibooks

Wechseln zu: Navigation, Suche

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 O(p~\log_2 b) 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.
Persönliche Werkzeuge