4. Millionär durch Primzahlenformel?

Millionär durch Primzahlenformel?

  • ?

    Blue-Tiger schrieb:

    Du meinst mit "wieviel Geld ist damit zu machen" oder mit "Formel != Algorithmus"?

    Eigentlich meine ich den ganzen Thread.
    Der Link der auf das letzte Posting leitet war etwas unglücklich gewählt.

    0
  • M

    Christoph schrieb:

    Primzahl schrieb:

    Wer hat denn in diesem Thread recht:

    http://www.forum-3dcenter.org/vbulletin/showthread.php?s=14c30fdfba561c286a5b2ed0c8287899&p=7812105#post7812105

    Kann man so nicht sagen. Da fehlt die genaue Definition von "Formel". Ich würde jedenfalls nicht behaupten, dass Formel != Algorithmus ist, ohne erstmal zu definieren, was ich eigentlich mit "Formel" meine.

    Man kann ja schreiben (als "Formel"):

    n-te Primzahl=min{k∈N∣π(k)=n}\text{n-te Primzahl} = \min \{ k \in \mathbb{N} \mid \pi(k) = n \}

    wobei $$\pi(k)$$ die Anzahl der Primzahlen kleiner oder gleich k ist. Das ist natürlich ziemlich sinnlos.

    Wie wärs mit: Eine Formel ist ein Algorithmus mit O(1)?

    0
  • C
    Mod

    Mr.Fister schrieb:

    Wie wärs mit: Eine Formel ist ein Algorithmus mit O(1)?

    Das wäre auf jeden Fall eine mögliche Definition.

    Andererseits möchte man vielleicht auch sowas als "Formel" zulassen:
    \begin{align*}\text{L\"osung} = x^2\end{align*}
    Wenn x eine natürliche Zahl ist, die im Computer explizit dargestellt wird, dann ist x^2 nicht in O(1) implementierbar.

    edit: OK, hängt davon ab, welche Operationen man mit dem Groß-O zählt. Du zählst primitive Rechenoperationen wohl als O(1), dann gilt mein Beispiel natürlich nicht.

    0
  • Mod

    Mr.Fister schrieb:

    Wie wärs mit: Eine Formel ist ein Algorithmus mit O(1)?

    Ungünstig. Dann kann man nämlich keine Reihenentwicklungen oder so verwenden.

    0
  • B

    Der gesuchte Begriff heißt effizienter Algorithmus.

    0
  • ?

    Was heißt effizient?

    0
  • ?

    effizient ist polynomiell

    0
  • ?

    was soll denn überhaupt eingabe und ausgabe sein

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

    0
  • ?

    oder noch besser

    Eingabe: n
    Ausgabe: n-te Primzahl

    und das O(1)

    ach keine ahnung

    sorry für spam

    0
  • ?

    _ 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.

    0
  • B

    Das ist eine sinnlose Definition:

    1. Sie sagt nur, was eine Formel _nicht_ sein soll. Ist ein Weihnachtsgeschenk eine Formel? Mist, eine Schleife dran, aber du verstehst worauf ich hinauswill?
    2. Man kann jeden Algorithmus ohne Schleifen formulieren.
    3. 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?
    0
  • ?

    Bashar schrieb:

    1. 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.

    0
  • O

    Primzahl schrieb:

    Bashar schrieb:

    1. 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

    0
  • K

    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.

    0
  • ?

    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?

    0
Anmelden zum Antworten