Vorwort
Heute habe ich eine Frage gesehen, die den Anschein hat, dass es nicht schwierig war zu bestimmen, ob eine Zahl eine Primzahl ist. Deshalb habe ich mich entschlossen, es umzusetzen.
Dom -Struktur
<! DocType html> <html Lang = "en"> <head> <meta charset = "utf-8"> <title> Berechnen Sie Prime-Nummern innerhalb von 500 und Ausgabe </title> <meta name = "viewPort" content = "width = develce-width, initial-scale = 1.0, maximal-scale = 1.0, ebas-scalable = 0". src = "http://apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"> </script> </head> <body> <div> <Eingabe type = "text" id = "num" value = "" value = "subieren"> </div> </body> </html> <skript> $ (function () {$ ("#subieren"). On ('click', function () {var num = $ ("#num"). val (); if (iSprimenum (num)) {alert (num+"is Prime"); Composite ");}});}); </script>Wie oben gezeigt, verwenden wir die Funktion iSprimenum (NUM), um festzustellen, ob es sich um eine Primzahl handelt. Implementieren wir diese Funktion unten.
Verwenden Sie die For -Loop, um festzustellen, ob es sich um eine Primzahl handelt
Funktion isPrimenum (num) {für (var i = 2; i <num; i ++) {if (num%i == 0) {return false;}}; return true;}Das Prinzip ist relativ einfach. Wenn Sie den Rest ständig mit der Zielnummer mit 2 oder mehr finden, bedeutet dies, dass dies eher eine zusammengesetzte Zahl als eine Primzahl ist.
Aber diese Berechnung scheint etwas groß zu sein
Optimieren Sie die erste Methode
Es ist sehr einfach, es wird in kurzer Zeit implementiert. Es scheint jedoch, dass wir es optimieren können. Wir müssen diese Zahl nicht jagen und den Rest finden. Wir müssen nur die Hälfte dieser Zahl verlaufen, um zu berechnen, ob diese Zahl eine Primzahl ist.
Funktion isSprimenum (num) {für (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}}; return true;}Nach der tatsächlichen Messung wurde die Geschwindigkeit tatsächlich stark verbessert, aber ich weiß, dass der Mantissa der Zahl gerade oder 5 ist, sodass sie definitiv keine Primzahl ist, sodass sie nicht berechnet werden müssen. Lassen Sie es uns erneut optimieren
Keine Berechnungszahlen, deren Mantissa gerade oder 5 ist
Funktion isPrimenum (num) {if (! isDual (num)) {return false;} für (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}}; num.substring (num.length-1, num.length); return deTnum%2 == 0 || Lastnum%5 == 0? Falsch: wahr;}Durch eine solche Optimierung können wir die Berechnung und mindestens der Hälfte der Anzahl reduzieren. (Aber die tatsächliche Messung verbessert die Leistung, da solche Zahlen schnell beurteilt werden können, dass sie keine Primzahlen sind)
Hier fand die Funktion substring (), dass sie nicht für Zahlen verwendet werden kann, sondern nur für Zeichenfolgen verwendet werden kann. Leider wird die Nummer zuerst in eine Zeichenfolge verwandelt.
Wenn es sich nicht um eine Nummer oder eine Ganzzahlverarbeitung handelt
Was soll ich tun, wenn der Benutzer keine Nummer oder eine Dezimalstelle ist? Ich schrieb schnell zwei Methoden, um es zu verarbeiten ...
Funktion isSprimenum (num) {if (! isnum (num)) {return false;} if (! isIntenger (num)) {return false;} if (! isDual (num)) {return false;} für (var i = 2; i <num/2+1; Issineger (num) {return num == ~~ num? Richtig: False;} Funktion isnum (num) {var num = num.toString (); var dandnum = num.substring (num.Length-1, num.Length); return Lastnum%2 == 0 || Lastnum%5 == 0? Falsch: wahr;}Hier werden zwei Tipps verwendet, eine ist, die Dezimalzahlen zu runden, und der andere ist, Strings in Zahlen umzuwandeln. +num.
Bitte lesen Sie meinen vorherigen Blog -Beitrag "JS tun vor, Fähigkeiten für JavaScript Learning (i) von Fungleo" vorzustellen. "
Dies verbessert keine Effizienz, sondern beseitigt nur die Berechnungsfehlereingabe. Denken wir noch einmal darüber nach, gibt es eine Möglichkeit, schnell festzustellen, ob es sich nicht um eine Primzahl handelt?
Entfernen Sie Zahlen, die durch 3 teilbar sein können, und berechnen Sie nicht
Funktion isSprimenum (num) {if (! isnum (num)) {return false;} if (! isinterger (num)) {return false;} if (num == 2 || num == 3 || num == 5) {return true;} if (! Num/5+1; Richtig: False;} Funktion isnum (num) {return num == +num? TRUE: False;} Funktion isDual (num) {var num = num.toString (); var haftnum = num.substring (Num.Length-1, num.Length); return Lastnum%2 == 0 || Lastnum%5 == 0? false: true;} Funktion isthree (num) {var str = num.toString (); var sum = 0; für (var i = 0; i <str.length; i ++) {sum+=+str.substring (i, i+1);}; Return Sum%3 == 0? Falsch: wahr;}Hier verwandeln wir die Nummer zuerst in eine Zeichenfolge, teilen dann jedes Bit der Zeichenfolge, addieren und summe und verwenden das Ergebnis und 3, um die verbleibenden zu ermitteln, und dann können wir herausfinden, ob diese Zahl durch 3 getrennt werden kann.
Haha, ich bin so schlau ... Die tatsächliche Testleistung hat sich nicht viel verbessert, aber sie hat sich tatsächlich ein wenig verbessert. Es ist ein wenig deprimiert
Wenn wir jedoch die 3-aufgelegte Zahl ausschließen, müssen wir nicht die Hälfte davon berechnen. Wir müssen nicht die Hälfte davon berechnen, wir müssen nur ein Drittel berechnen. Außerdem haben wir auch 5 ausgeschlossen, daher müssen wir nur ein Fünftel berechnen ...
Nach schnellen Anpassungen wurde die Effizienz erheblich verbessert !!! Ich bin mächtig ...
Auf diese Weise bestimmt der Code jedoch, dass es sich um eine zusammengesetzte Nummer in 2/3/5 handelt. Daher muss ein anderer Satz hinzugefügt werden.
if (num == 2 || num == 3 || num == 5) {return true;}Methoden anderer Leute
Dann konnte ich mir keine Optimierungsmethode vorstellen ... also habe ich die folgende Lösung gesucht und gefunden. Ich war schockiert !!!
Funktion isPrimenum2 (num) {return!/^.? $ |^(..+?)/1+$/. test (Array (num+1) .Join ('1')}Die reguläre Methode wird verwendet, es ist in der Tat kurz, aber ich kann sie verstehen, auch wenn ich sie lese !!!
Ich verstehe wirklich nicht, was das Prinzip ist, also habe ich einen praktischen Test gemacht und festgestellt, dass meine Code -Effizienz viel höher ist als dieser Code. Daraus können wir sehen, dass meine Methode immer noch sehr ausgezeichnet ist !!
Es dauert 1600 ms, damit mein Code alle Prime -Nummern innerhalb von 100000 druckt, und dieser Code dauert 160000 ms. Das heißt, mein Code dauert nur ein Prozent der Zeit.
Wenn jemand diesen Code verstehen kann, erklären Sie ihn mir bitte ...
Wieder auffüllen
Nach dem Lesen einiger verwandter Informationen scheint die Methode, die ich oben verwendet habe, nicht sehr gut (das Ergebnis ist nicht falsch). Es gibt einen besseren Weg, nämlich Math.SQRT (Num) zu verwenden, um die Quadratwurzel zu finden.
Meine Code -Testergebnisse sind wie folgt
Wie in der obigen Abbildung gezeigt, ist das Berechnungsergebnis meines Codes vollständig korrekt. Es dauerte jedoch 1638 Millisekunden. Nach vielen Tests ist es immer noch der Fall.
Die Testergebnisse der Quadratwurzelmethode sind wie folgt
Wie in der obigen Abbildung gezeigt, ist diese Methode wissenschaftlicher und schneller. Es dauert mehrere Tests und dauert zwischen 1150 Millisekunden und 1250 Millisekunden. Im Vergleich zu meiner Codeleistung sind es ungefähr 25%.
Ich beurteile auch, ob die Ziffern gerade oder 5 sind und ob die Summe durch 3 geteilt werden kann, was lange her ist. Ich hoffe definitiv, die Menge an Operationen zu reduzieren. Diese Codes selbst haben aber auch die Menge an Operationen. Ich werde meinen gesamten Code entfernen und ihn dann ansehen.
Die Leistung wurde wieder verbessert. Es scheint, dass alle meine Berechnungen negativ optimiert sind!
Schließlich lautet der Code wie folgt:
Funktion isPrimenum (num) {if (! isnum (num)) {return false;} if (! isinterger (num)) {return false;} für (var i = 2; i <= math.sqrt (num); i ++) {if (num%i == 0) {return false;}}; Richtig: False;} Funktion isnum (num) {return num == +num? Richtig: false;}Zusammenfassung: Es war ausschließlich an meiner schlechten Arithmetik, die mich dazu veranlasste, an der Vorderseite klug zu sein. Das Üben kleiner Techniken ist jedoch auch gut -_- |||
Lassen Sie uns schließlich einen Blick darauf werfen, wie lange es dauert, um alle Primzahlen innerhalb von 1 Million zu berechnen
Die oben genannte Zusammenfassung der Methoden zur Beurteilung, ob eine Nummer eine vom Herausgeber eingeführte Primzahl ist. Ich hoffe, es wird für alle hilfreich sein.