Primzahlen: Programmbeispiele

Primzahlen

Sieb des Eratosthenes

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

Prinzip

Das Sieb des Eratosthenes ist ein Verfahren, um alle natürlichen Zahlen (ferner nur mit „Zahlen“ bezeichnet) bis zu einer vorgegebenen Zahl n, einschließlich n selbst, auf Primalität zu testen (zu Primzahlen siehe auch die Seite Primfaktorisierung) und, sofern sie prim sind, auszugeben. Das Sieb des Eratosthenes "zäumt das Pferd von hinten auf": Es werden alle Zahlen bis n (inklusive) größer als 1 hintereinander aufgeschrieben. Dann werden die Zahlen der Reihe nach durchgegangen. Die echten Vielfachen der aktuellen Zahl (für 3 z. B. 6, 9, 12, ...) werden durchgestrichen. Übrig bleiben die Zahlen $x_{i}$, die keine echten Vielfachen einer Zahl echt zwischen 1 und $x_{i}$ sind. Dies sind sämtliche Primzahlen bis zur vorgegebenen Grenze.

Beispiel

Sei $n=10$. Hintereinander werden die Zahlen 2, 3, 4, 5, 6, 7, 8, 9, 10 aufgeschrieben. Die 2 wird betrachtet und ihre echten Vielfachen weggestrichen: 2, 3, 4, 5, 6, 7, 8, 9, 10. Dasselbe für die 3: 2, 3, 4, 5, 6, 7, 8, 9, 10. Übrig sind noch 2, 3, 5 und 7. Dies sind, wie wir überprüfen können, alle Primzahlen im betrachteten Intervall, sodass hier abgebrochen werden kann. Schritte, um das Verfahren zu optimieren, damit der Algorithmus wirklich schon so früh endet, werden im nächsten Absatz besprochen.

Optimierungen eines simplen Durchgehens aller Zahlen und ihrer echten Vielfachen

Es müssen nur die Zahlen bis einschließlich $\lfloor {\sqrt {n}}\rfloor$ betrachtet werden, wobei $\lfloor \rfloor$ den ganzzahligen Anteil (die Abrundungsfunktion) symbolisiert. Denn sei $n>x>\lfloor {\sqrt {n}}\rfloor$, dann gilt für die Vielfachen: $\ p\cdot x\leq n\Longleftrightarrow p\leq {\frac {n}{x}}<{\sqrt {n}}$, alle Vielfachen von $x$ wurden also bereits als Vielfache von $2\leq p<{\sqrt {n}}\$gestrichen.

Bereits gestrichene Zahlen müssen nicht mehr betrachtet werden, da ihre echten Vielfachen garantiert durch einen echten Teiler der gestrichenen Zahl teilbar sind.

Weiter optimieren kann man unter anderem, indem man das Wegstreichen der echten Vielfachen einer Zahl $p$ erst bei $p^{2}$ beginnt. Denn alle Vielfachen $<p^{2}$ sind von der Form $y\cdot p$ mit $y<p$. Damit wurden sie aber als ganzzahlige Vielfachen einer kleineren Zahl schon überprüft.

Komplexitätstheoretische Beschreibung

Durch diese und weitere Optimierungen lässt sich die Laufzeit auf $O(n\log {\log {n}})$ reduzieren. Beim Vergleich verschiedener Implementierungen und Varianten des Algorithmus ist die Ordnung der Laufzeit aber nur bedingt von Nutzen, da sie Konstanten außer Acht lässt. Bei diesem speziellen Problem wird der Sachverhalt bei einem Vergleich verschiedener Varianten auch bei großen n offensichtlich.

Die Speicherplatzkomplexität lässt sich auf $O({\frac {\sqrt {n}}{\log {n}}})$ drücken.

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.

> 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

Siehe hierzu Gambas:_Rechnen#Primzahlen_berechnen

Visual Basic 3

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

Möglichkeit 1

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 Konsole ausgegeben.

public class Primzahlen {

    public static void main(String[] args) {
        int limit = 100;
        int zahl;      // Zu überprüfende Zahl
        int zaehler;   // Hilfsvariable (möglicher Teiler von zahl)
        boolean primzahl; // Hilfsvariable, ob die aktuelle Zahl eine Primzahl ist

        // zahl <= x   ist der zu überprüfende Zahlenraum
        // Beginn bei 2, weil 1 per Definition keine Primzahl ist
        for (zahl = 2; zahl <= limit; zahl++) {
            // solange wir für zahl keinen Teiler finden, gehen wir davon aus,
            // dass es eine Primzahl ist
            primzahl = true;

            // zaehler ist ein möglicher Teiler. Mögliche nicht-triviale Teiler
            // liegen im Bereich 2 bis zahl/2 (abgerundet), wenn x aber Teiler
            // von Zahl und größer als Wurzel(zahl), ist zahl/x < Wurzel(zahl), 
            // sodass diese Grenze genügt.
            for (zaehler = 2; zaehler < Math.sqrt(zahl) + 1; zaehler++) {
                if (zahl % zaehler == 0) {
                    // zaehler ist ein nichttrivialer Teiler von zahl und damit
                    // zahl keine Primzahl. Weitere Teiler müssen nicht geprüft
                    // werden und damit kann die Schleife abgebrochen werden.
                    primzahl = false;
                    break;
                }


            }

            if (primzahl) {
                // Keine Teiler gefunden -> zahl2 ist eine Primzahl
                System.out.println(zahl+" ist eine Primzahl");
            }
        }
    }
}

Möglichkeit 2

Dies ist eine lauffähige Implementierung der brute-force-Version des Siebes von Eratosthenes mit leichten Optimierungen. Die main()-Funktion lässt sich z. B. zum Testen nutzen. Zuerst wird eine Liste erzeugt, die Map-Einträge enthält, welche eine Zahl und ihren Status (durchgestrichen?) repräsentieren.
Zur Erzeugung eines einzelnen Map-Eintrages brauchte ich das Objekt java.util.AbstractMap.SimpleEntry<K, V>, da Map.Entry als Interface keinen Konstruktor besitzt. Dies ist die eleganteste und schnellste Lösung, ansonsten hätte ich ein komplettes Set mit den Werten erzeugen, dessen Einträge durch Iteration über Set.entrySet() an eine Liste anhängen und diese dann sortieren müssen (bestmögliche Komplexität einer vergleichsbasierten Sortierung: $O(n\log {n})$), da selbst bei Maps, die SortedMap implementieren, entrySet() nicht zwingend sortiert ist.
Nach Abschluss der Durchstreich-Phase werden die noch nicht durchgestrichenen Zahlen in eine Liste geschrieben und als Ergebnis zurückgegeben.

// Benötigt Java 8!

import java.util.*;

public class Primzahlgenerator {

    public static void main(String[] args){

    }

    public static List<Integer> siebDesErasthotenes(int obereGrenze){
        // Prüft sämtliche ganzen Zahlen echt zwischen 1 und der oberen Grenze sowie die obere Grenze selber auf Primalität
        List<AbstractMap.SimpleEntry<Integer, String>> kandidaten = new ArrayList<>();

        List<Integer> ergebnis = new ArrayList<Integer>();

        String gestrichen = "gestrichen";
        String unberuehrt = "unberührt";

        for(int i = 2; i <= obereGrenze; i++){
            kandidaten.add(new AbstractMap.SimpleEntry<>(i, unberuehrt));
        }
       
        int element;
        int index;

        for (int i = 0; i < kandidaten.size() / 2 + 1; i++){
            if (!(kandidaten.get(i).getValue().equals(gestrichen))) {
                element = kandidaten.get(i).getKey();
                index = 2 * element - 2; // Index des nächsten Vorkommens
                while (index < kandidaten.size()) {
                    (kandidaten.get(index)).setValue(gestrichen);  // ArrayList.get in O(1)!
                }
            }
        }
        
        for (Map.Entry<Integer, String> eintrag: kandidaten){
            if (eintrag.getValue() == unberuehrt) {
                ergebnis.add(eintrag.getKey());
            }
        }
        
        return ergebnis;
    }
}

C#

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

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];
            //Zuerst alle Zahlen von 2 bis n als Primzahl markieren
            for (int i = 2; i < n; i++)
            {
                prime[i] = true;
            }

            //Einzelner Abschnitt
            {
                //Wir wollen bei 2 anfangen
                int i = 2;

                //Alle Produkte des Teilers i
                //angefangen bei 2, bis kleiner n durchlaufen
                //Wenn n = 50, dann ist bei i = 7 Schluss, weil das Produkt = 49 ist
                for (; i * i < n; i++)
                {
                    //Wenn die Zahl im Array als Primzahl markiert ist
                    //Was bei den ersten beiden 2 und 3 definitiv der Fall ist
                    if (prime[i])
                    {
                        //Primzahl bis Wurzel(n) ausgeben
                        Console.WriteLine(i);
                        //Alle weiteren Produkte des Teilers i
                        //angefangen beim Produkt i * i bis kleiner n durchlaufen
                        //j wird mit i beim nächsten Durchlauf (Vielfaches) addiert
                        for (int j = i * i; j < n; j += i)
                        {
                            //Dies kann unmöglich eine Primzahl sein
                            //weil es ein Vielfaches von i ist.
                            prime[j] = false;
                        }
                    }
                }

                //Alle Primzahlen ausgeben
                for (; i < n; i++)
                {
                    if (prime[i])
                    {
                        Console.WriteLine(i);
                    }
                }
            }
            
            Console.ReadLine();
        }
    }
}

Delphi

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

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

Theoretisch ein endloser Primzahl-Generator – nur durch die Hardware begrenzt –, aber langsamer als Siebe. Er nutzt den Satz von Wilson in umgestellter Form. Der Programmlauf wird durch Strg-C gestoppt.

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys, time

def pgen():
  ''' ... generates the sequence of all primes: 2,3,5,7,11 ... 
  '''

  p=2
  f=1

  try:

    ts2=time.time()

    while(True):

      if f%p%2: sys.stdout.write(str(p)+"\n")
      p+=1
      f*=(p-2)

  except:

#   raise KeyboardInterrupt .. Ctrl-C

    ts2-=time.time()
    sys.stderr.write("time: "+str(round(-ts2,3))+" sec\n")

def main():
  pgen()
  sys.exit()

if __name__=="__main__":
  main()

Python 2

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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]: # 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:
            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.

#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;
}

Eine andere Variante, die neuere Sprachfeatures (Lambdas, automatische Typableitung - C++11) sowie Container und Algorithmen der Standard Template Library (STL) benutzt, ist die nachfolgende. Dabei wird das Erase-Remove-Idiom benutzt: Der STL-Algorithmus remove_if schiebt alle Elemente des std::vector-Containers, die das durch ein Lambda-Konstrukt ([p](auto q){ ... }) formulierte Teilbarkeits-Kriterium erfüllen, ans Ende des Containers und gibt einen Iterator, der auf den Anfang des zu löschenden Bereiches zeigt, zurück. Mit candidates.erase(..., end(candidates)) schließlich wird der gesamte Bereich gelöscht (was intern lediglich eine Änderung der Längen-Variablen des Containers bedeutet).

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

vector<unsigned>  primes_upto(unsigned limit)
{
    vector<unsigned>    candidates(limit - 1);
    iota(begin(candidates), end(candidates), 2);    // candidates = 2, 3, ..., n

    auto const  upper_limit = (limit + 1) / 2;      // ceil(limit/2)

    for (auto candidate = begin(candidates);        // vector<unsigned>::iterator
         *candidate <= upper_limit;
         ++candidate)
    {
        auto const p = *candidate;                

        // 'erase-remove idiom':
        // remove_if(...) moves all multiples of p to the end and returns
        // an iterator to the beginning of the (re)moved part;
        // candidates.erase(..., end(candidates)) actually deletes these values
        candidates.erase(remove_if(candidate + 1,   // don't remove p itself
                                   end(candidates),
                                   [p](auto q){     // capture p by value
                                       return (q % p == 0);
                                   }),
                         end(candidates));

    }

    return candidates;      // copy elision guaranteed by C++ standard
}

int main()
{
    unsigned limit;
 
    cout << "Please insert upper limit.\n";
    cin >> limit;

    auto primes = primes_upto(limit);

    for (auto p : primes)
        cout << p << " ";

    cout << endl;
}

R

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

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

Go

Hier ein möglicher Quelltext eines Go-Programms zur Ausgabe der Primzahlen von 1-1000 (Der Bereich kann natürlich beliebig erweitert werden). Die Primzahlen werden dann in der Console ausgegeben. Dieses Programm kann auf der offiziellen Golang-Seite ausprobiert werden. Die Erklärungen sind identisch mit denen vom Java-Quellcode.

package main

import "math"

func main () {
	var limit uint = 1000
	var zahl, zaehler uint
	var primzahl bool
	
	for zahl = 2; zahl <= limit; zahl++ {
		
		primzahl = true
		
		for zaehler = 2; zaehler <= zahl/2; zaehler++ {
			if math.Mod(float64(zahl), float64(zaehler)) == 0 {
				primzahl = false
				break
			}
		}
		
		if primzahl == true {
			println(zahl, " ist eine Primzahl")
		}
	}
	
	
}