Primzahlen: Programmbeispiele

Sieb des Eratosthenes

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

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.

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

Gambas

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

• Siehe Gambas:_Rechnen#Primzahlen_berechnen

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.

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

Java

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

Code

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#

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

Code

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

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

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.

Python 2

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

Code

#!/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++

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

Code

#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

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

Code

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