Ist die Genauigkeit von nextProbablePrime() mit der Größe des Eingabewerts verknüpft?

Question

Ich benutze BigInteger in einer Hausaufgabe, um die nächste Primzahl zu berechnen, die ich verwenden kann, um eine Hash-Tabelle, die quadratische Probing verwendet, zu ändern.

Die Tabelle speichert Daten, die aus einer Datei eingelesen wurden. Die Beispieldatei, die ich erhalten habe, enthält nur 100 Elemente, aber ich kann nicht davon ausgehen, dass dies der maximale Datensatz ist, auf dem mein Programm getestet wird.

Ich frage mich, ob es eine Beziehung zwischen der Größe des Wertes, den ich an nextProbablePrime übergeben, und der Wahrscheinlichkeit, dass es eine Primzahl korrekt zurückgibt? Mit anderen Worten, gibt es eine Zahl, unter der nextProbablePrime garantiert genau ist? Ist es vernünftig, sich darauf zu verlassen?

Answer 1

Da "die Wahrscheinlichkeit, dass die durch diese Methode zurückgegebene Zahl zusammengesetzt ist, 2^-100 nicht überschreitet" Ich denke, es ist vernünftig für Sie anzunehmen, sich auf die Rückgabe einer Primzahl zu verlassen.

Answer 2

nextProbablePrime() wird eigentlich für kryptografische Operationen verwendet, die (wirklich) große Zahlen suchen, die "wahrscheinlich prim" sind. Die Methode nextProbablePrime() gibt eine Zahl mit einer Wahrscheinlichkeit von 2^-100 als Primzahl zurück.

Ich glaube nicht, dass eine solche Methode für Ihre Bedürfnisse nützlich ist. Für angemessene Zahlen (wie die Größe einer Hashtabelle) können Sie einfach überprüfen, ob eine Zahl prim ist, indem Sie eine einfache, selbst erstellte Implementierung verwenden, insbesondere wenn eine hohe Leistung erforderlich ist.

Answer 3

Es ist gut für Ihren Zweck.

Besser wäre es, eine vorberechnete Liste von Hash-Tabellengrößen zu verwenden. Du brauchst wahrscheinlich nur ein halbes Dutzend oder so; Wählen Sie basierend auf der erwarteten Größe Ihrer Hash-Tabelle und wachsen Sie, wenn der Ladefaktor zu groß wird.

Die allgemeine Lektion besteht darin, alle möglichen Methoden zu nehmen, um die Komplexität Ihres Codes zu reduzieren. Sie schreiben eine Hashtabelle. Sie müssen sich keine Gedanken über Primzahlen machen.