Primzahlgenerator

Primzahlgenerator

Als Primzahlgenerator bezeichnet man in der Informatik einen Algorithmus f(n), so dass für natürliche Zahlen n der Wert f(n) die n-te Primzahl ist. Bisher wurde noch kein effektiver Primzahlgenerator gefunden, insbesondere existiert keine Formel zur Generierung von Primzahlen. Ein trivialer Primzahlgenerator kann folgendermaßen induktiv definiert werden:

  1. f(1) = 2
  2. f(2) = 3
  3. für n > = 3 ist f(n + 1) die auf f(n) folgende Primzahl, wobei einfach alle Zahlen ab f(n) + 2 aufsteigend darauf getestet werden, ob sie eine Primzahl sind.

Dieses Verfahren ist aber recht ineffektiv, da nacheinander alle ungeraden natürlichen Zahlen getestet werden müssen. Als Alternative bietet es sich an, mittels einer Siebmethode eine genügend lange Liste von Primzahlen zu erstellen und diese dann bis zur gewünschten Primzahl zu durchlaufen.


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • GIMPS — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Lucas-Lehmer Test — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersenne-Primzahlen — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersenne-Zahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersennesche Zahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersennsche Primzahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Primzahl — Die Zahl 12 ist keine Primzahl. Eine Primzahl ist eine natürliche Zahl, die größer als eins und ausschließlich durch sich selbst und durch eins teilbar ist. Eine Primzahl ist also eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”