Prefacio
Hoy vi una pregunta que hizo que pareciera que no era difícil determinar si un número es un número primo. Por lo tanto, decidí implementarlo.
Estructura dom
<! Doctype html> <html lang = "en"> <head> <meta charset = "utf-8"> <title> Calcule los números primos dentro de 500 y salida </title> <meta name = "viewport" content = "width = dispositivo-width, inicial-escale = 1.0, maximum-scale = 1.0, usledsable = 0"> <script <script <script <script <script <script <script. src = "http://apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"> </script> </head> <body> <div> <input type = "text" id = "num" value = "> <input type =" button "id =" enviar " valor = "enviar"> </div> </body> </html> <script> $ (function () {$ ("#envíquito"). on ('click', function () {var num = $ ("#num"). val (); if (isPrimeNum (num)) {alerta (num+"es prime");} else {num+"iss iss it compuesto ");}});}); </script>Como se muestra arriba, usamos la función ISPrimenum (NUM) para determinar si es un número primo. Implementemos esta función a continuación.
Use el bucle for para determinar si es un número primo
función isPrimenum (num) {for (var i = 2; i <num; i ++) {if (num%i == 0) {return false;}}; return true;}El principio es relativamente simple. Al encontrar constantemente el resto con el número objetivo con 2 o más, si puede obtener 0, significa que este es un número compuesto en lugar de un número primo.
Pero este cálculo parece ser un poco grande
Optimizar el primer método
Es muy simple, se implementa en poco tiempo. Sin embargo, parece que podemos optimizarlo. No tenemos que perseguir este número y encontrar el resto. Solo necesitamos recorrer a la mitad de este número para calcular si este número es un número primo.
función isPrimenum (num) {for (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}}; return true;}Después de la medición real, la velocidad se ha mejorado enormemente, pero sé que la mantissa del número es uniforme o 5, por lo que definitivamente no es un número primo, por lo que no hay necesidad de calcularla. Vamos a optimizarlo de nuevo
No hay números de cálculo cuya Mantissa sea uniforme o 5
función isPrimenum (num) {if (! isDual (num)) {return false;} for (var i = 2; i <num/2+1; i ++) {if (num%i == 0) {return false;}}; return true;} function isDual (num) {var num = num.ToString (); var lastnum = num.substring (num.length-1, num.length); return LastNum%2 == 0 || LastNum%5 == 0? falso: verdadero;}A través de dicha optimización, podemos reducir la cantidad de cálculo y al menos la mitad del número. (Pero la medición real mejora el rendimiento, porque tales números se pueden juzgar rápidamente que no son números primos)
Aquí, la función Substring () descubrió que no se puede usar en números, pero solo se puede usar en cadenas. Lamentablemente, el número se convierte primero en una cadena.
Si no es un número o procesamiento entero
¿Qué debo hacer si el usuario ingresa no es un número o un decimal? Rápidamente escribí dos métodos para procesarlo ...
función isPrimenum (num) {if (! isNum (num)) {return false;} if (! isInTeger (num)) {return false;} if ( iSInteger (num) {return num == ~~ num? verdadero: falso;} función isNum (num) {var num = num.ToString (); var lastNum = num.substring (num.length-1, num.length); return lastNum%2 == 0 || LastNum%5 == 0? falso: verdadero;}Aquí se usan dos puntas, uno es redondear el número decimal ~~, y el otro es convertir cadenas a números. +NUM.
Lea mi publicación de blog anterior "JS Fingending Habilidades para JavaScript Learning (I) de Fungleo"
Esto no mejora ninguna eficiencia, pero solo elimina la entrada de error de cálculo. Pensemos nuevamente en ello, ¿hay alguna forma de determinar rápidamente si no es un número primo?
Eliminar números que pueden ser divisibles por 3 y no calcule
function isPrimeNum(num){if (!isNum(num)){return false;}if (!isInteger(num)){return false;}if (num==2||num==3||num==5) {return true;}if (!isDual(num)){return false;}if (!isThree(num)){return false;}for (var i = 2; i < num/5+1; verdadero: falso;} función isnum (num) {return num == +num? Verdadero: falso;} function isDual (num) {var num = num.ToString (); var lastNum = num.substring (num.length-1, num.length); return lastNum%2 == 0 || LastNum%5 == 0? falso: true;} función istthree (num) {var str = num.ToString (); var sum = 0; for (var i = 0; i <str.length; i ++) {sum+=+str.substring (i, i+1);}; return sum%3 == 0? falso: verdadero;}Aquí, primero convertimos el número en una cadena, luego dividimos cada bit de la cadena, agregamos y sumamos, y usamos el resultado y 3 para encontrar el restante, y luego podemos averiguar si este número puede separarse por 3.
Jaja soy tan inteligente ... el rendimiento de la prueba real no ha mejorado mucho, pero de hecho ha mejorado un poco. Está un poco deprimido
Sin embargo, si excluyimos el número 3 dividido, entonces no tenemos necesidad de calcular la mitad de él. No tenemos necesidad de calcular la mitad, solo necesitamos calcular un tercio. Además, también hemos excluido 5, por lo que solo necesitamos calcular un quinto ...
¡Después de ajustes rápidos, la eficiencia se ha mejorado enormemente! Soy poderoso ...
Sin embargo, de esta manera, el código determinará que es un número compuesto en 2/3/5. Por lo tanto, se debe agregar otra oración.
if (num == 2 || num == 3 || num == 5) {return true;}Métodos de otras personas
Entonces no pude pensar en un método de optimización ... así que busqué y encontré la siguiente solución. Estaba sorprendido !!!
función isPrimenum2 (num) {return!/^.? $ |^(..+?)/1+$/. test (array (num+1) .Join ('1'))}El método regular se usa, de hecho es corto, ¡pero puedo entenderlo incluso si lo leo!
Realmente no entiendo cuál es el principio, así que tomé una prueba práctica y descubrí que la eficiencia de mi código es mucho más alta que este código. ¡De esto podemos ver que mi método sigue siendo muy excelente!
Mi código tarda 1600 ms para imprimir todos los números primos dentro de 100000, y este código toma 160000 ms. Es decir, mi código solo toma el uno por ciento del tiempo.
Sin embargo, si alguien puede entender este código, explícame a mí ...
Reponer
Después de leer información relacionada, parece que el método que utilicé NUM/5 anterior no es muy bueno (el resultado no está mal). Hay una mejor manera, que es usar Math.SQRT (NUM) para encontrar la raíz cuadrada.
Los resultados de mi prueba de código son los siguientes
Como se muestra en la figura anterior, el resultado del cálculo de mi código es completamente correcto. Sin embargo, tardó 1638 milisegundos. Sigue siendo el caso después de muchas pruebas.
Los resultados de la prueba del método de raíz cuadrada son los siguientes
Como se muestra en la figura anterior, este método es más científico y más rápido. Se necesitan múltiples pruebas y se necesitan entre 1150 milisegundos y 1250 milisegundos. En comparación con el rendimiento de mi código, es alrededor del 25%.
También juzgo si los dígitos son uniformes o 5, y si la suma puede dividirse por 3, lo que ha sido mucho tiempo. Definitivamente espero reducir la cantidad de operaciones. Pero estos códigos en sí también tienen la cantidad de operaciones. Eliminaré todo mi código y luego lo miraré.
El rendimiento se ha mejorado nuevamente. ¡Parece que todos mis cálculos están optimizados negativamente!
Finalmente, el código es el siguiente:
function isPrimenum (num) {if (! isNum (num)) {return false;} if (! isInTeger (num)) {return false;} for (var i = 2; i <= math.sqrt (num); i ++) {if (num%i == 0) {return false;}}; return true;} function isinteger (num) {num = ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~~ verdadero: falso;} función isnum (num) {return num == +num? verdadero: falso;}Resumen: se debió completamente a mi pobre aritmética lo que me llevó a ser inteligente en el frente. Sin embargo, practicar pequeñas técnicas también es buena -_- |||
Finalmente, echemos un vistazo a cuánto tiempo lleva calcular todos los números primos dentro de 1 millón
Lo anterior es un resumen de los métodos para juzgar si un número es un número primo introducido por el editor. Espero que sea útil para todos.