Zuordnung natürliche Zahlen Primzahlen

Question

kennt jemand eine Zuordnungsfunktion, die jeder natürlichen Zahl eine Primzahl zuordnet?

Answer 1

Bilde (n-1)! und addiere 1. Prüfe, ob sich das Ergebnis durch n teilen lässt. Wenn ja, dann liegt eine Primzahl vor.

Zugegeben, keine einfache Zuordnung, aber wenn du etwas einfaches findest, wirst du berühmt.

Answer 2

Unter

http://www.gerdlamprecht.de/Primzahlen.htm

findest Du eine 3-fach-Summenformel für die bekannte Funktion Prime(x).

hier eine kleine Wertetabelle (jeder natürlichen Zahl x ist ein Funktionsergebnis zugeordnet):

x | Prime(x)

1 | 2

2 | 3

3 | 5

1000 | siehe http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

(Wert von 1e24 ist auch bekannt!; größere Werte per Näherungsfunktion)

An dieser Funktion sieht man auch, warum die kleinste Primzahl 2 ist.

Nachteil: durch die 3 Summen wird die Laufzeit exponentiell langsam -> d.h. nicht für große Argumente geeignet.