Ich kämpfe darum zu sehen, wie wir eine Liste von J kleinsten Primzahlen in Poly-Zeit J erzeugen können, basierend auf der Tatsache, dass p "j kleiner oder gleich ist 2j * ln(j) für j> 2, wobei j die j-te aufeinanderfolgende Primzahl angibt. Zum Beispiel p1 = 2 für j = 1, p2 = 3 für j = 2. p3 = 5 für j = 3, p4 = 7 für j = 4, p5 = 11 für j = 5 usw. etc ...
Ich sehe einfach nicht, wie ich diese Tatsache nutzen kannüber. Jedes Mal, wenn ich eine Primzahl erzeugen möchte, sagen wir die 7., werde ich das überprüfen, indem ich einschließe: 2 (7) * ln (7) = 27.2427 ... Aber das ist völlig nutzlos, wie sich herausstellt. Diese Zahl ist viel größer als die letzte generierte Primzahl in meinem Array, was logisch ist. Daher muss ich immer noch auf rohe Gewalt zurückgreifen, indem ich die letzte Primzahl + 1 für mod0 mit jeder der Primzahlen in meinem Array überprüfe. Die andere Option besteht darin, auf bereits existierende Algorithmen zurückzugreifen, die die Zeit auf Polynomzeit reduzieren.
Können Sie mir zeigen, wie ich diese Tatsache nutzen kann: p "j <= 2j * ln (j)? Danke.
Antworten:
3 für die Antwort № 1Um zu zeigen, dass ich eine Liste der ersten J Primzahlen in Zeitpolynom in J erzeugen kann, muss ich die Kosten berechnen, wie auch immer ich die Liste erzeuge.
Wenn ich die Liste durch Überprüfung der Nummern erzeugeNacheinander und dem Verwerfen von Nicht-Primzahlen gibt es zwei Teile zu den Kosten der Erzeugung der Liste - wie lange es dauert, um jede Nummer zu prüfen, und wie viele Nummern ich überprüfen muss.
Wenn Primzahlen verschwindend selten waren, dann konnte ich es nichtleisten, jede Nummer von 2 an zu überprüfen, weil einfach alle diese Nummern aufzulisten wäre zu teuer. Aber wenn ich weiß, dass die J-te Primzahl nicht größer als 2j * ln (j) ist, kann ich sie wenigstens alle in polynomieller Zeit auflisten.
In der Tat, wenn ich J Primzahlen erzeugen muss, und ichBeginnen Sie, indem Sie die ersten 2J * ln (J) Zahlen nehmen, und ich entscheide mich, jede Zahl als Prim zu prüfen, indem ich sie durch jede Primzahl dividiere. Ich habe nie mehr als J Primzahlen zur Hand, also kann ich nicht am Ende mehr als 2J ^ 2 * ln (J) Trial Divisionen. Das wird mir keinen Preis für Effizienz oder clevere Algorithmen oder sogar scharfe Grenzen für den Rechenaufwand bringen, aber es ist nicht schlechter als das Polynom.
2 für die Antwort № 2
Vielleicht ist es, dass Sie denken, dass die obere Grenze Ihnen ein gibt Methode um die j-te Primzahl oder die ersten j Primzahlen direkt zu erzeugen. Es tut nicht - es gibt dir nur ein Größenbeschränkung auf der Menge der Zahlen, die Sie mit einer Methode überprüfen müssen, die Sie schon herumliegen hatten, z. Probeabteilung.
Wenn ich Ihnen eine Liste der n-1 Zahlen 2, 3, ..., n gebe und Sie auffordern alle Primzahlen in dieser Liste zu finden, können Sie dies mit Hilfe der Trial Division in O (n ^ 2) Zeit tun:
- Überprüfen Sie für jedes Zahlenpaar x und yob x gleichmäßig in y einteilt und y durchkreuzt, wenn es so ist. Dieser Schritt ist O (n ^ 2) und erfordert O (n) Raum, um zu verfolgen, welche Zahlen durchgestrichen wurden.
- Listen Sie alle Nummern auf, die nicht durchgestrichen sind. Dieser Schritt ist O (n).
Beachten Sie, dass dies alle Primzahlen <= n in O (n ^ 2) für findet irgendein positiver Wert von n. Wenn wir also einen Wert von j erfahren, wird es für n = RoundDown (2j log j) funktionieren.
Mit n = RoundDown (2j log j) wird dieser Algorithmus ausgeführtin der Zeit O ((2j log j) ^ 2) = O (j ^ 2 log ^ 2 j), die in j polynomial ist, und es muss mindestens die ersten j Primzahlen finden, da die Schranke uns sagt, dass die jth prime kann höchstens RoundDown sein (2j log j), und wir haben jede Zahl bis einschließlich dieser Zahl in unsere Eingabeliste aufgenommen. (Es kann noch mehr Primzahlen finden, aber wir können sie bei Bedarf in linearer Zeit verwerfen.)
Übung: Denken Sie darüber nach, warum wir umrunden dürfen Nieder Hier.