0 Daumen
1,1k Aufrufe

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

Avatar von

2 Antworten

0 Daumen

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.

Avatar von 123 k 🚀
0 Daumen

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.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community