kennt jemand eine Zuordnungsfunktion, die jeder natürlichen Zahl eine Primzahl zuordnet?
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.
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.
Ein anderes Problem?
Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos