Ich versuche, den Lucas-Lehmer-Test (LLT) für Mersenne-Zahlen zu implementieren ( Ссылка ). Es sollte polynomial und daher schnell sein. Hier ist mein Code:
%Vor%Hier ist der Versuch, den oben implementierten Algorithmus zu verwenden: Ссылка
Wenn ich Anzahl der Ziffern versuche, die kleiner als 7 ist, ist alles in Ordnung, aber wenn ich versuche, nach Primzahl mit mindestens 7 Ziffern zu fragen, stolpert das Programm einfach und gibt keine Antwort.
Bitte, hilf mir. Was ist falsch an meiner Algorithmus-Implementierung oder was ist falsch an meinem Programm selbst?
Wenn ich den Code auf Ссылка mit dieser Änderung ausführe:
%Vor%Dann endet es für (scheinbar) eine beliebige Anzahl von Ziffern. Die Ergebnisse scheinen jedoch falsch zu sein: Es gibt Nicht-Primzahlen mit mehr Ziffern als angefordert aus.
Das Problem ist, dass Javascript Modulo auf negative Ergebnisse auswerten kann. Zum Beispiel wird -2 % 5 -2 sein. Dies ist mathematisch korrekt, aber die meisten Informatikalgorithmen erfordern positive Werte, also 3 in diesem Fall.
Durch das Hinzufügen von M in dieser Formel wird sichergestellt, dass das Ergebnis unabhängig von den sprachlichen Eigenarten positiv ist.
Das Problem mit falschen Ergebnissen ist wahrscheinlich auf die Tatsache zurückzuführen, dass Sie diese Anforderung nicht befolgen:
Der Lucas-Lehmer-Test funktioniert wie folgt. Sei Mp = 2 ** p - 1 die Mersenne-Zahl, um mit p eine ungerade Primzahl zu testen .
Die p gibt es in Ihrem Code n . Nirgends stellen Sie sicher, dass n prim ist.
Dann gibt es auch, dass Javascript Integer-Typ möglicherweise nicht groß genug ist. Mit n größer als 23 beginnt es seine Grenzen zu erreichen. Zum Beispiel gibt es keine Mersenne Prime mit 7 Ziffern. Der nächste ist mit 10 Ziffern, das ist 2**31 - 1 .
Sie werden es jedoch nicht in (reinem) JavaScript finden können, da die Berechnung die Quadrierung von 2**31 - 1 , überschreitet die Grenzen der Ganzzahlen von JavaScript .
Tags und Links javascript algorithm primes