Préface
Aujourd'hui, j'ai vu une question qui a fait semblant qu'il n'était pas difficile de déterminer si un nombre est un nombre privilégié. Par conséquent, j'ai décidé de l'implémenter.
Structure DOM
<! Doctype html> <html lang = "en"> <éad> <meta charset = "utf-8"> <itle> Calculer les nombres premiers dans 500 et la sortie </Title> <meta name = "Viewport" contenu = "width = device-width, initial-SCALE = 1.0, maximum-scale = 1.0, user-scalable = 0"> <brit-scal src = "http://apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"> </ script> </ head> <body> <div> <input type = "text" id = "num" value = ""> <entrée type = "bouton" id = "soumis" Value = "Soumide"> </div> </ body> </html> <script> $ (function () {$ ("# soumed"). on ('click', function () {var num = $ ("# num"). val (); if (isprimenum (num)) {alert (num + "is prime");} else {alert (num + "est composite ");}});}); </script>Comme indiqué ci-dessus, nous utilisons la fonction isPrimenum (NUM) pour déterminer s'il s'agit d'un nombre premier. Implémentons cette fonction ci-dessous.
Utilisez la boucle pour déterminer s'il s'agit d'un nombre premier
fonction isPrimeum (num) {for (var i = 2; i <num; i ++) {if (num% i == 0) {return false;}}; return true;}Le principe est relativement simple. En trouvant constamment le reste avec le numéro cible avec 2 ou plus, si vous pouvez obtenir 0, cela signifie qu'il s'agit d'un numéro composite plutôt que d'un nombre premier.
Mais ce calcul semble être un peu grand
Optimiser la première méthode
C'est très simple, il est mis en œuvre dans un court moment. Cependant, il semble que nous puissions l'optimiser. Nous n'avons pas à poursuivre ce nombre et à trouver le reste. Nous avons juste besoin de boucler à la moitié de ce nombre pour calculer si ce nombre est un nombre premier.
fonction isPrimeum (num) {for (var i = 2; i <num / 2 + 1; i ++) {if (num% i == 0) {return false;}}; return true;}Après la mesure réelle, la vitesse a en effet été considérablement améliorée, mais je sais que la mantissa du nombre est uniforme ou 5, donc ce n'est certainement pas un nombre premier, il n'est donc pas nécessaire de le calculer. Optimions-le à nouveau
Pas de nombres calculants dont la mantissa est égale ou 5
Fonction isPrimeum (num) {if (! isDual (num)) {return false;} for (var i = 2; i <num / 2 + 1; i ++) {if (num i == 0) {return false;}}; return true;} fonction isdual (num) {var num = num.tostring (); var lastnum = num.substring (num.length-1, num.length); return lastnum% 2 == 0 || Lastnum% 5 == 0? Faux: vrai;}Grâce à une telle optimisation, nous pouvons réduire la quantité de calcul et au moins la moitié du nombre. (Mais la mesure réelle améliore les performances, car ces chiffres peuvent être rapidement jugés qu'ils ne sont pas des nombres premiers)
Ici, la fonction substring () a révélé qu'elle ne peut pas être utilisée sur les nombres, mais ne peut être utilisée que sur les chaînes. Malheureusement, le numéro est donc transformé en une chaîne en premier.
Si ce n'est pas un numéro ou un traitement entier
Que dois-je faire si les entrées de l'utilisateur ne sont pas un nombre ou une décimale? J'ai rapidement écrit deux méthodes pour le traiter ...
fonction isPriMenum (num) {if (! isNum (num)) {return false;} if (! isInteger (num)) {return false;} if (! isDual (num)) {return false;} for (var i = 2; i <num / 2 + 1; i ++) {if (num% i == 0) {return false;}}; isInteger (num) {return num == ~~ num? Vrai: false;} fonction isNum (num) {var num = num.toString (); var lastnum = num.substring (num.length-1, num.length); return lastnum% 2 == 0 || Lastnum% 5 == 0? Faux: vrai;}Deux conseils sont utilisés ici, l'un consiste à arrondir la décimale ~~ num, et l'autre consiste à convertir les chaînes en nombres. + num.
Veuillez lire mon article de blog précédent "JS Prétendant les compétences pour l'apprentissage JavaScript (i) par Fungleo"
Cela n'améliore aucune efficacité, mais élimine uniquement l'entrée d'erreur de calcul. Réfléchissons-y à nouveau, y a-t-il un moyen de déterminer rapidement s'il ne s'agit pas d'un nombre privilégié?
Supprimer les nombres qui peuvent être divisibles par 3 et ne calculent pas
Fonction 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 (! istree (num)) {return false;} pour (Vars pour 2; num / 5 + 1; i ++) {if (num% i == 0) {return false;}}; return true;} function isInteger (num) {return num == ~~ num? vrai: false;} fonction isNum (num) {return num == + num? Vrai: false;} fonction isDual (num) {var num = num.toString (); var lastnum = num.substring (num.length-1, num.length); return lastnum% 2 == 0 || Lastnum% 5 == 0? FAUX: true;} fonction iSTree (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? Faux: vrai;}Ici, nous transformons d'abord le nombre en une chaîne, puis divisons chaque bit de la chaîne, ajoutez et sommez, et utilisons le résultat et 3 pour trouver le reste, puis nous pouvons savoir si ce nombre peut être séparé par 3.
Haha je suis si intelligent ... les performances de test réelles ne se sont pas beaucoup améliorées, mais elle s'est en effet un peu améliorée. C'est un peu déprimé
Cependant, si nous excluons le nombre à 3 divisions, nous n'avons pas besoin de calculer la moitié de celui-ci. Nous n'avons pas besoin de calculer la moitié de celui-ci, nous n'avons qu'à calculer un tiers. De plus, nous avons également exclu 5, nous avons donc juste besoin de calculer un cinquième ...
Après des ajustements rapides, l'efficacité a été considérablement améliorée !!! Je suis puissant ...
Cependant, de cette manière, le code déterminera qu'il s'agit d'un numéro composite au 2/3/5. Par conséquent, une autre phrase doit être ajoutée.
if (num == 2 || num == 3 || num == 5) {return true;}Méthodes des autres
Ensuite, je ne pouvais pas penser à une méthode d'optimisation ... alors j'ai recherché et trouvé la solution suivante. J'ai été choqué !!!
fonction isprimenum2 (num) {return! / ^.? $ | ^ (.. +?) / 1 + $ /. test (array (num + 1) .join ('1'))}La méthode régulière est utilisée, elle est en effet courte, mais je peux le comprendre même si je le lis !!!
Je ne comprends vraiment pas quel est le principe, alors j'ai passé un test pratique et j'ai constaté que mon efficacité de code est beaucoup plus élevée que ce code. De cela, nous pouvons voir que ma méthode est toujours très excellente !!
Il faut 1600 ms à mon code pour imprimer tous les nombres premiers à 100000, et ce code prend 160000 ms. C'est-à-dire que mon code ne prend qu'un pour cent du temps.
Cependant, si quelqu'un peut comprendre ce code, veuillez me l'expliquer ...
Remplir
Après avoir lu certaines informations connexes, il semble que la méthode que j'ai utilisée NUM / 5 ci-dessus ne soit pas très bonne (le résultat n'est pas faux). Il existe un meilleur moyen d'utiliser Math.sqrt (num) pour trouver la racine carrée.
Mes résultats de test de code sont les suivants
Comme le montre la figure ci-dessus, le résultat de calcul de mon code est complètement correct. Cependant, il a fallu 1638 millisecondes. C'est toujours le cas après de nombreux tests.
Les résultats des tests de la méthode de la racine carrée sont les suivants
Comme le montre la figure ci-dessus, cette méthode est plus scientifique et plus rapide. Il faut plusieurs tests, et il faut entre 1150 millisecondes et 1250 millisecondes. Par rapport à mes performances de code, il est d'environ 25%.
Je juge également si les chiffres sont égaux ou 5, et si la somme peut être divisée par 3, ce qui a été longtemps. J'espère vraiment réduire le montant des opérations. Mais ces codes eux-mêmes ont également le nombre d'opérations. Je vais supprimer tout mon code, puis le regarder.
Les performances ont été à nouveau améliorées. Il semble que tous mes calculs soient optimisés négativement!
Enfin, le code est le suivant:
fonction isPrimeum (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;}}; vrai: false;} fonction isNum (num) {return num == + num? vrai: faux;}Résumé: C'est entièrement à cause de mon pauvre arithmétique qui m'a amené à être intelligent à l'avant. Cependant, pratiquer de petites techniques est également un bon -_- |||
Enfin, jetons un coup d'œil à combien de temps il faut pour calculer tous les nombres premiers dans un million
Ce qui précède est un résumé des méthodes pour juger si un nombre est un nombre premier introduit par l'éditeur. J'espère que ce sera utile à tout le monde.