Primzahlen: Programmbeispiele

Aus Wikibooks
Wechseln zu: Navigation, Suche

Sieb des Eratosthenes[Bearbeiten]

Die Spezifikation des Algorithmus in Pseudocode ist in der Wikipedia zu finden.

Haskell[Bearbeiten]

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.

Code[Bearbeiten]

> 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

Gambas[Bearbeiten]

Ein Programmbeispiel zur Primzahlberechnung findet sich im Wikibuch der Programmiersprache Gambas.

Visual Basic 3[Bearbeiten]

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.

Code[Bearbeiten]

 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

Java[Bearbeiten]

Hier ein möglicher Quelltext eines Java-Programms zur Ausgabe der Primzahlen von 1-100 (Der Bereich kann natürlich beliebig erweitert werden). Die Primzahlen werden dann in der Console ausgegeben.

Code[Bearbeiten]

public class Primzahlen
{
	public static void main(String[] args)
	{
		int limit = 100;
		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 <= limit; 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 <= zahl; zaehler++)	// Es empfiehlt sich den Terminationswert auf zahl zu 
                                                                                //setzen und nicht auf limit, da die Berechnung von Primzahlen 
                                                                                //bis zu Milliardenbeträgen sonst nur äußerst langsam 
                                                                                //funktioniert. Die Teilung durch Zahlen, die größer sind als 
                                                                                //die zu überprüfende Zahl selbst ist ohne hin obsolet.
 
				{
					zahl2 = zahl % zaehler;			// Division der Ausgangszahl durch eine weitere und ablegen des Rests 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");*/
			}
		}
	}
}

C#[Bearbeiten]

Folgende eigenständig lauffähige Konsolenanwendung (.NET 2.0) gibt alle Primzahlen bis n nach dem Sieb des Eratosthenes aus:

Code[Bearbeiten]

using System;
using System.Collections.Generic;
using System.Text;
 
namespace eratosthenes
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 100;
            bool[] prime = new bool[n];
            for (int i = 2; i < n; i++)
                prime[i] = true;
 
            for (int i = 2; i < n; i++)
                if (prime[i])
                {
                    Console.WriteLine(i);
                    for (int j = i * i; j < n; j = j + i)
                        prime[j] = false;
                }
 
            Console.ReadLine();
        }
    }
}

Delphi[Bearbeiten]

Folgende Konsolenanwendung gibt mit Hilfe der Funkton isPrim() von einer bestimmten Zahlenmenge die Primzahlen aus.

Code[Bearbeiten]

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.

Python 2[Bearbeiten]

Dieses Script bittet den Benutzer zuerst nach einer Obergrenze und gibt danach alle Primzahlen bis zu dieser Grenze aus.

Code[Bearbeiten]

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
import sys
 
def main():
 
    # Frage den Benutzer nach einer Obergrenze bis zu der gesucht werden soll
    while True:
        try:
            obergrenze = int(raw_input('Bitte geben Sie eine Obergrenze ein: '))
            break
 
        except ValueError:
            print 'Dies ist keine gültige Obergrenze. Bitte verwenden Sie eine Ganzzahl!'
 
    # Jede Zahl zwischen 1 und obergrenze wird zuerst als prim angenommen
    zahlen = [True]*(obergrenze+1)
    # Da 0 und 1 keine Primzahlen sind, werden sie auf False gesetzt
    zahlen[0] = False
    zahlen[1] = False
 
    i = 2
 
    while i*i <= obergrenze:
        if zahlen[i] == True: # Die Zahl i ist als prim markiert
            # Streiche alle Vielfachen von i
            for k in range(i*i,obergrenze+1,i):
                zahlen[k] = False
 
        i = i+1
 
    # Ausgabe aller gefundenen Zahlen
    for i, v in enumerate(zahlen):
        if v == True:
            print i, 'ist prim.'
 
    return 0
 
if __name__ == '__main__':
    main()

C++[Bearbeiten]

Das Programm fragt zunächst nach einer Obergrenze und gibt dann alle Primzahlen bis zu dieser aus.

Code[Bearbeiten]

#include<iostream>
#include<cmath>
using namespace std;
 
int main(void){
    unsigned limit;
 
    cout << "Please insert upper limit.\n";
    cin >> limit;
 
    bool *Stroke = new bool[limit+1];
    Stroke[0]=1;
    Stroke[1]=1;
    for(unsigned i=2; i<=limit; ++i) Stroke[i] = 0;
 
    unsigned prime=2;
    while(pow((double)prime,2.0)<=limit){
        for(unsigned i = (int)pow((double)prime,2.0); i<=limit; i+=prime){
            Stroke[i]=1;
        }
 
        do ++prime; while(Stroke[prime]);
    }
 
    cout << "\nPrimes less or equal " << limit << " are:\n";
    for(unsigned i=0; i<=limit; ++i){
        if(!Stroke[i]) cout << i << endl;
    }
    delete[] Stroke;
 
    return 0;
}

R[Bearbeiten]

Limit heißt die Obergrenze, bis zu der alle Primzahlen ausgegeben werden.

Code[Bearbeiten]

sieb<-function(limit){
 (vek<-2:limit)[1==apply(0==outer(vek, vek, "%%"), 1, sum)]
   # Primzahlen bis limit
   # %% Division mit Rest oder modulo
}