Kann die Primzahlfunktion und das Produkt von aufeinanderfolgenden Primzahlen in Polynomialzeit berechnet werden?

Question

In beiden Algorithmen Ich habe mit gearbeitet, verwende ich die zwei Funktionen:

1. pi (n): = Anzahl der Primzahlen < = n und
2. R (n): = r, wo prod (p_i, i = 1, r) = n < aber n < prod (p_i, i = 1, r + 1), wop_i den i-te Primzahl ist.

Grundsätzlich pi (n) ist die berühmte prime-Zählfunktion, und R (n) berechnet, nur das Produkt der aufeinanderfolgenden Primzahlen bis Sie die gebundenen n und geben die Menge von Primzahlen verwendet, zu erreichen, so zum Beispiel:

R (12) = 2, da 2 * 3 < = 12, aber 2 * 3 * 5> 12 und beispielsweise

R (100) = 3, weil 2 * 3 * 5 < = 100 aber 2 * 3 * 5 * 7> 100.

Mit meinem Professor haben wir über die Laufzeit der Berechnung dieser Funktionen gesprochen. Ich weiß, dass das pi (n), dass es in etwa x/ln (x) im Laufe der Zeit, aber ich habe meine Zweifel über einige Sachen:

1. Kann R (n) in Polynomialzeit berechnet werden? Aus meiner Sicht können wir mit dynamischer Programmierung die Produkte 2 * 3 * 5 * ... * p_i berechnen, indem wir 2 * 3 * 5 * ... * p_ (i-1) kennen, also reduziert sich das Problem auf bekomme die nächste Primzahl, die, soweit ich weiß, in polynomieller Zeit berechnet werden kann (PRIMES ist in P).
2. Auch weil wir wissen, dass wir bestimmen können, ob eine Zahl in Polynomialzeit Primzahl ist, sollte das nicht heißen, dass Pi (n) in Polynomialzeit berechnet werden kann? (Auch dynamische Programmierung kann hilfreich sein).

Wenn mir jemand helfen kann, diese Fragen zu klären oder mich auf die richtige Richtung zu weisen, würde ich es wirklich schätzen! Vielen Dank!

Answer 1

Für jedes n, können Sie leicht bestimmen, ob es Prime in O (n^(1/2)) Zeit (überprüfen Sie die Teilbarkeit von 2,3,4 ..., sqrt (n)), so könnten Sie Iterieren Sie einfach über n und behalten Sie einen Zähler, wie Sie gehen. Wenn Sie Ihre Primzahlen in einer Liste speichern, können Sie es sogar beschleunigen, indem Sie prüfen, ob jede Zahl Primzahl ist (achten Sie auf Teilbarkeit von 2,3,5 ..., am nächsten Primzahl zu sqrt (n)). Also sollte dieser Algorithmus zum Auffinden von Pi (n) O (n^(3/2)) sein.

Angenommen, Sie führen diesen Algorithmus aus und speichern die Primzahlen in einer Liste. Dann könnten Sie für R (n) einfach durch sie iterieren, um ihr kumulatives Produkt zu erhalten, und zurückkehren, sobald Sie n überschreiten. Ich bin mir nicht sicher, wie hoch die zeitliche Komplexität ist, aber es wird klein sein. Wahrscheinlich etwas nach O (log (n)), sicherlich etwas schneller als O (n). Setzen Sie beide zusammen und Sie sollten etwas schneller als O (n^(5/2)) bekommen.

Answer 2

Es gibt Methoden, um Pi (n) in sublinearer Zeit zu berechnen. Google für "Legende Phi" oder für "Lehmer Hauptzählfunktion", oder für neuere Arbeit "lagarias Miller Odlyzko Prime Zählfunktion". Lehmers Methode ist nicht schwer zu programmieren; Ich diskutiere es unter my blog.