Java & JavaScript


Home
Applets
   3D:
 · Würfel
 · Würfel 2
 · Würfel 3
 · Tetraeder
 · Tetraeder 2
 · Dodekaeder
 · Ikosaeder
 · Fußball
 · Kugel
 · Kugel 2
   Fraktale:
 · Apfelmännchen
 · Apfelmännchen 2
 · Apfelmännchen 3
 · Apfelmännchen MA
 · Apfelmännchen Zoom
 · Apfelmännchen Zoom 2
 · Juliamenge
 · Juliamenge MA
 · Julia-Generator
 · Koch-Kurve
 · Koch-Kurve 2
 · Hilbert-Kurve
 · Sierpinski-Dreieck
 · Sierpinski-Dreieck 2
 · Sierpinski-Dreieck 3
 · Sierpinski-Teppich
 · Pythagoras Baum
 · Lindenmayer-System
 · Lindenmayer-System 2
   Mathematik:
 · Funktionsplotter
 · Eratosthenes-Sieb
 · Miller-Rabin-Test
   Verschiedenes:
 · Morsezeichen-Ticker
 · Analoguhr
Scripts
Gäste
Kontakt



Primes and Programming: An Introduction to Number Theory with Computing
- Anzeige -


- Applets : Mathematik : Eratosthenes-Sieb -


Ein Primzahlen-Test nach dem 'Sieb des Eratosthenes' als Java-Applet.

Streicht man aus der Menge natürlicher Zahlen von 2 bis n, beginnend mit 2, nacheinander alle Vielfachen der jeweils noch verbleibenden Zahlen heraus, enthält die Restmege nur noch Primzahlen. Dieses Verfahren zur Primzahlen-Gewinnung ist als "Sieb des Eratosthenes" bekannt. (Nach Eratosthenes von Kyrene, hellenistischer Gelehrter, um 276-195 v. Chr.)


[Primzahlen-Test mit dem Eratosthenes-Sieb als Java-Applet zum Download. Das Eratosthenes-Applet kann die Primzahlen allerdings nur mit aktiviertem Java testen !]


Das "Sieb des Eratosthenes" funktioniert im klassischen Sinne folgendermaßen:

1. Schreibe alle natürlichen Zahlen von 2 bis zu einer beliebigen Zahl n auf.
2. Streiche alle Vielfachen von 2 heraus.
3. Gehe zur nächstgrößeren nichtgestrichenen Zahl und streiche deren Vielfache heraus.
3. Wiederhole 3. sooft es geht.
4. Die übriggebliebenen Zahlen sind Primzahlen.

Zum Beispiel:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ...
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ...
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ...
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ...

=> Primzahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ...

Carl Friedrich Gauß (dt. Mathematiker, 1777-1855) soll nach diesem Muster angeblich die ersten drei Millionen Zahlen nach Primzahlen durchsiebt haben (handschriftlich !).

Dem obigen Beispiel lässt sich auch anschaulich entnehmen, wie mit dem Sieb-Verfahren eine individuelle Zahl (hier 31) als Primzahl erkannt werden kann. Indem diese nämlich alle Teilungsversuche (Streichungen) durch kleinere, bereits identifizierte Primzahlen übersteht.
Oft wird dieses Verfahren deshalb nur als Test durch "Probe-Division" bezeichnet, um es vom klassischen Streichverfahren des Eratosthenes' zu unterscheiden.

Wie auch immer er genannt wird, ein solcher Primzahlen-Tests ist bei Zahlen bis etwa 1.000.000.000.000 ein sehr gutes Verfahren, um schnell zu einer sicheren Antwort zu gelangen. Darüber hinaus steigt die Rechendauer jedoch stark an und macht den Test bald ineffizient.

Einige Testergebnisse zur Einschätzung der ungefähren Rechendauer (900 MHz):

10.000.000.019 (prim, 0 Sekunden)
100.000.000.003 (prim, 1 Sekunde)
1.000.000.000.039 (prim, 3 Sekunden)
10.000.000.000.037 (prim, 11 Sekunden)
100.000.000.000.031 (prim, 48 Sekunden)
1.000.000.000.000.037 (prim, 4 Minuten)
10.000.000.000.000.061 (prim, 17 Minuten)
100.000.000.000.000.003 (prim, 88 Minuten)
1.000.000.000.000.000.003 (prim, 7 Stunden)
9.223.372.036.854.775.783 (prim, 32 Stunden)


Eratosthenes.java
(In Kurzform. Vollständiger Code im Download)

import java.awt.*;
import java.applet.*;

public class Eratosthenes extends Applet {

  public void init() {
    isPrime([Testzahl]);
  }

  public void isPrime(long x) {

    int i, j=0;
    long n=3;
    long primes[] = new long[5602];

    primes[0] = 2;

    boolean xPrime = true, nPrime;

    if (x%2==0 && x!=2) {
      xPrime = false;
      n = 2;
    }

    xWhile: while (n<=Math.sqrt(x)) {

      i = 0;
      nPrime = true;

      nWhile: while(primes[i]*primes[i]<=n) {
        if (n%primes[i]==0) {
          nPrime = false;
          break nWhile;
        }
        i++;
      }
      if (nPrime) {
        if (x%n==0) {
          xPrime = false;
          break xWhile;
        }
        if (j<5601) primes[j++] = n;
      }
      n+=2;
    }

    if (xPrime) System.out.println("\n"+x+" ist eine Primzahl !");
    else System.out.println("\n"+x+" = "+n+"*"+Long.toString(x/n));
  }
}

Es ist nur die Umsetzung des oben beschriebenen Verfahrens. Nacheinander werden alle notwendigen Primzahlen ermittelt und durch die zu prüfende Zahl geteilt.

Erklärungsbedürftig ist vielleicht die relativ kleine Größe des Arrays von nur 5.602, um immerhin Zahlen bis 9.223.372.036.854.775.807 zu überprüfen:
Benötigt werden zur Prüfung von x ja nur Primzahlen bis zur Quadratwurzel von x. Die größte dieser Primzahlen selbst benötigt aber ebenso nur eine Prüfung bis zu ihrer eigenen Wurzel. Die Primzahlen, die also mehrfach gebraucht werden und deshalb ins Array müssen, sind alle Primzahlen unterhalb der vierten Wurzel von 2^63-1 ~ 55.108 und das sind genau 5.601. Plus 1, um die Abbruchbedingung zu erreichen, ergibt maximal 5.602 abzuspeichernde Primzahlen.


Eratosthenes von Kyrene

(Eratosthenes von Kyrene)


Download  Eratosthenes.zip (Applet und Code, ca. 5 kb)




© 2001-2004 Albert Kluge - Alle Rechte vorbehalten
Impressum | Datenschutz | Nutzung | eMail