Millionär durch Primzahlenformel?

Was heißt effizient?

effizient ist polynomiell

was soll denn überhaupt eingabe und ausgabe sein

Vorschlag Eingabe: Primzahl, Ausgabe: nächsthöhere Primzahl und das effizient

oder noch besser

Eingabe: n
Ausgabe: n-te Primzahl

und das O(1)

ach keine ahnung

sorry für spam

_ schrieb:

oder noch besser

Eingabe: n
Ausgabe: n-te Primzahl

Ja, genau so.

Ich geb 51233 ein und bekomme die 51233. Primzahl.

Zur Definition was eine Formel ist würde ich sagen:
Eine Formel enthält keine Schleifen.

Damit kann man einen Algorithmus sehr gut von einer Schleife abgerenzen.

Bashar

Das ist eine sinnlose Definition:

Sie sagt nur, was eine Formel _nicht_ sein soll. Ist ein Weihnachtsgeschenk eine Formel? Mist, eine Schleife dran, aber du verstehst worauf ich hinauswill?
Man kann jeden Algorithmus ohne Schleifen formulieren.
Viele Dinge, die man als Laie eindeutig als Formel bezeichnen würde, enthalten bei geeigneter Interpretation des Begriffs Schleifen. Was ist 3 plus 4? Naja, man zählt viermal eins zu 3 dazu und bekommt 7. Was ist 3 mal 4? Was ist 3 hoch 4? Was ist mit durch unendliche Reihen definierten Funktionen wie der Sinusfunktion?

Bashar schrieb:

Man kann jeden Algorithmus ohne Schleifen formulieren.

Gut, dann ist die Definition eines Algorithmus eben, daß er aus Schleifen mit Bedinungen und somit Abzweigungen besteht.

otze

Primzahl schrieb:

Bashar schrieb:

Man kann jeden Algorithmus ohne Schleifen formulieren.

Gut, dann ist die Definition eines Algorithmus eben, daß er aus Schleifen mit Bedinungen und somit Abzweigungen besteht.

Gram-Schmidt-Orthonormalisierung enthält keine Schleifen mit Bedingungen. Ist aber ganz klar ein Algorithmus

knivil

Ok, der Primzahltest liegt in P. Dann muss man nur noch eine obere Schranke des Suchraums festlegen, der hoffentlich polynomiell von der Eingabegroesse (n-te Primzahl) abgeleitet werden kann und probiert dann alle durch ... tatatata polynomieller Algorithmus fuer die n-te Primzahl.

knivil schrieb:

Dann muss man nur noch eine obere Schranke des Suchraums festlegen, der hoffentlich polynomiell von der Eingabegroesse (n-te Primzahl) abgeleitet werden kann

Sicher? Zwischen 0 und x liegen etwa x/ln(x) primzahlen. ist da die inverse noch polynomiell?