Die Funktion Prime(x), die die x-te Primzahl erzeugt?

Question

auf http://www.gerdlamprecht.de/Primzahlen.htm steht die Funktion Prime(x), deren Beschreibung "Die Funktion Prime(x) und ihre Summendarstellung (erzeugt die x. Prinzahl)" lautet.

 

 

Erste Frage: Ich dachte, eine derartige Funktion gibt es nicht? Ich weiß nur, dass die innerste Summe von i=1 bis j die Teileranzahl von j ist.

Zweite Frage: Um sie zu testen habe ich sie mal in ein Programm umgeschrieben, das aber nicht funktioniert. Ich weiß nicht, ob es an der Funktion liegt oder an dem Programmcode.

        Dim Prime As Double = 0
        Dim x As Integer = 2

        Dim sumi As Double = 0
        Dim sumk As Double = 0
        Dim sumj As Double = 0

        Prime += 2
        For k As Integer = 2 To Floor(2 * x * Log(x) + 2)
            sumj = 0
            For j As Integer = 2 To k
                sumi = 0
                For i As Integer = 1 To j
                    sumi += Floor(j / i) - Floor((j - 1) / i)
                Next
                sumj += Floor((2 - sumi) / j) + 1
            Next
            sumk += 1 - Floor((1 / x) * sumj)
            Prime += sumk
        Next
        MsgBox(Prime)

Weiß jemand weiter?

 

Danke

Comments

Ach, den Fehler im Code habe ich jetzt gefunden. sumk += 1 - Floor((1 / x) * sumj) muss ausserhalb der äußersten Schleife sein, dann funktioniert es.

Okay, bleibt die erste Frage: Ich dachte so eine Funktion gibt es nicht... Und wenn (anscheinend) doch, warum ist sie nicht allzu bekannt?

---

Es gibt solche Funktionen, aber keine, die wirklich effizient arbeitet. Die Berechnung mit so einer Formel dauert ewig, deshalb sagt man meistens, dass es keine (wirklich effiziente) gibt. Kannst du auch bei deinem Programm ausprobieren für große x, das dauert schon lange.

---

Ja, habe ich auch schon gemerkt. Schon bei x = 30 dauert es über eine Sekunde. Ich dachte nur, es läge eine prinzipielle Unmöglichkeit vor, solche primzahlerzeugenden Funktionen aufzustellen... weil doch immer behauptet wird, "es gibt keine Funktion, die die Primzahlen erzeugt", dabei müsste es ja anscheinend eher heißen "es gibt keine effiziente Funktion, die die Primzahlen erzeugt, ineffiziente Funktionen gibt es aber"

Answer 1

Antwort mit KI erzeugt:

Erklärung und Fehler im Programmcode

Um Ihre Anfragen zu beantworten, gehen wir schrittweise durch die gestellten Fragen und den bereitgestellten Quellcode durch.

Erste Frage: Existenz einer Funktion Prime(x)

In der Mathematik gibt es tatsächlich keine explizite Formel, die direkt die \(x\)-te Primzahl generiert. Die auf der angegebenen Website beschriebene Funktion Prime(x) und ihre Beschreibung kann auf mathematisch interessante Ansätze hinweisen, insbesondere wenn es um Summationen und die Erzeugung von Primzahlen geht. Typischerweise ist der Ansatz zur Bestimmung der \(x\)-ten Primzahl iterativ oder basiert auf Siebmethoden wie dem Sieb des Eratosthenes, jedoch nicht auf einer einfachen, geschlossenen Formel. Das bedeutet, die Suche nach der \(x\)-ten Primzahl involviert üblicherweise das Prüfen von Kandidaten auf Primzahleigenschaften bis zur Erreichung der gewünschten Anzahl an Primzahlen.

Zweite Frage: Problem im Programmcode

Der bereitgestellte Code weist mehrere Problemstellen auf, die das erwartete Ergebnis beeinträchtigen könnten. Hier sind einige Korrekturen und eine mögliche Neufassung des Codes in einer beispielhaften Implementierung in Visual Basic.net (VB.net) inklusive der benötigten Korrekturen:

- Der Algorithmus versucht die Summationslogik zu nutzen, um die \(x\)-te Primzahl zu ermitteln, aber die Umsetzung scheint nicht korrekt zu sein.
- Es gibt ein logisches Problem beim Aktualisieren von Prime innerhalb der k-Schleife, was zu fehlerhaften Berechnungen führt.
- Die Floor-Funktion und ihre Anwendung im Kontext der Berechnungen sind korrekt, aber die Logik zur Ermittlung der Primzahl muss überprüft werden.

Korrigierter Ansatz (VB.net):

Um ein Programm zu schreiben, das die \(x\)-te Primzahl effizient findet, können wir eine einfachere und direktere Methode wie das Sieb des Eratosthenes verwenden oder einen iterativen Ansatz, der jede Zahl auf Primzahleigenschaften prüft, bis wir die \(x\)-te Primzahl erreichen. Hier ist ein vereinfachter VB.net Code, der einen einfachen, iterativen Ansatz darstellt:

vb.net
Function IsPrime(number As Integer) As Boolean
' Eine Funktion, um zu prüfen, ob eine Zahl eine Primzahl ist
If number <= 1 Then Return False
For i As Integer = 2 To Math.Sqrt(number)
If number Mod i = 0 Then Return False
Next
Return True
End Function

Function FindXthPrime(x As Integer) As Integer
' Funktion, die die x-te Primzahl findet
Dim count As Integer = 0
Dim number As Integer = 2
While count < x
If IsPrime(number) Then
count += 1
If count = x Then
Return number
End If
End If
number += 1
End While
Return -1 ' Falls x zu klein oder ein anderer Fehler auftritt
End Function

' Verwendung der Funktion:
Dim x As Integer = 10 ' Zehnte Primzahl suchen
Dim xthPrime As Integer = FindXthPrime(x)
Console.WriteLine("Die " & x & ". Primzahl ist: " & xthPrime)


In diesem Code:
- Die Funktion IsPrime prüft, ob eine gegebene Zahl eine Primzahl ist, indem sie durch alle Zahlen bis zu ihrer Quadratwurzel teilt.
- Die Funktion FindXthPrime verwendet IsPrime, um Primzahlen zu finden, bis sie die \(x\)-te Primzahl erreicht.

Obwohl dieser Ansatz funktioniert, kann er für sehr große \(x\) ineffizient sein. Für solche Fälle wären optimierte Algorithmen oder Siebmethoden vorzuziehen.