Preface
Today I saw a question that made it seem that it was not difficult to determine whether a number is a prime number. Therefore, I decided to implement it.
DOM structure
<!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><title>Calculate prime numbers within 500 and output</title><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0"><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="submit" value="submit"></div></body></html><script>$(function(){$("#submit").on('click',function(){var num = $("#num").val();if (isPrimeNum(num)) {alert(num+" is prime");}else{alert(num+" is composite");}});});</script>As shown above, we use the isPrimeNum(num) function to determine whether it is a prime number. Let's implement this function below.
Use the FOR loop to determine whether it is a prime number
function isPrimeNum(num){for (var i = 2; i < num; i++) {if (num%i==0){return false;}};return true;}The principle is relatively simple. By constantly finding the remainder with the target number with 2 or more, if you can get 0, it means that this is a composite number rather than a prime number.
But this calculation seems to be a bit large
Optimize the first method
It's very simple, it's implemented in a short while. However, it seems that we can optimize it. We don't have to chase this number and find the remainder. We just need to loop to half of this number to calculate whether this number is a prime number.
function isPrimeNum(num){for (var i = 2; i < num/2+1; i++) {if (num%i==0){return false;}};return true;}After actual measurement, the speed has indeed been greatly improved, but I know that the mantissa of the number is even or 5, so it is definitely not a prime number, so there is no need to calculate it. Let's optimize it again
No calculating numbers whose mantissa is even or 5
function 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 ? false : true;}Through such optimization, we can reduce the amount of calculation and at least half of the number. (But the actual measurement improves performance, because such numbers can be quickly judged that they are not prime numbers)
Here, the substring() function found that it cannot be used on numbers, but can only be used on strings. Sadly, so the number is turned into a string first.
If it is not a number or integer processing
What should I do if the user inputs is not a number or a decimal? I quickly wrote two methods to process it...
function 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;}};return true;}function isInteger(num){return num == ~~num ? true : false;}function isNum(num){var num = num.toString();var lastNum = num.substring(num.length-1,num.length);return lastNum%2 == 0 || lastNum%5 == 0 ? false : true;}Two tips are used here, one is to round the decimal ~~num, and the other is to convert strings to numbers. +num.
Please read my previous blog post "JS Pretending Skills for JavaScript Learning (I) by FungLeo"
This does not improve any efficiency, but only eliminates the calculation error input. Let's think about it again, is there any way to quickly determine whether it is not a prime number?
Remove numbers that can be divisible by 3 and do not calculate
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; i++) {if (num%i==0){return false;}};return true;}function isInteger(num){return num == ~~num ? true: false;}function isNum(num){return num == +num ? true : false;}function isDual(num){var num = num.toString();var lastNum = num.substring(num.length-1,num.length);return lastNum%2 == 0 || lastNum%5 == 0 ? false : true;}function isThree(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 ? false : true;}Here, we first turn the number into a string, then split each bit of the string, add and sum, and use the result and 3 to find the remaining, and then we can find out whether this number can be separated by 3.
Haha I'm so smart... The actual test performance has not improved a lot, but it has indeed improved a little. It's a little depressed
However, if we exclude the 3-divided number, then we have no need to calculate half of it. We have no need to calculate half of it, we only need to calculate one-third. In addition, we have also excluded 5, so we just need to calculate one-fifth...
After quick adjustments, the efficiency has been greatly improved!!! I am powerful...
However, in this way, the code will determine that it is a composite number in 2/3/5. Therefore, another sentence needs to be added.
if (num==2||num==3||num==5) {return true;}Other people's methods
Then I couldn't think of an optimization method... So I searched and found the following solution. I was shocked!!!
function isPrimeNum2(num){return !/^.?$|^(..+?)/1+$/.test(Array(num + 1).join('1'))}The regular method is used, it is indeed short, but I can understand it even if I read it!!!
I really don’t understand what the principle is, so I took a practical test and found that my code efficiency is much higher than this code. From this we can see that my method is still very excellent!!
It takes 1600ms for my code to print all prime numbers within 100000, and this code takes 160000ms. That is to say, my code only takes one percent of the time.
However, if anyone can understand this code, please explain it to me...
Replenish
After reading some related information, it seems that the method I used num/5 above is not very good (the result is not wrong). There is a better way, which is to use Math.sqrt(num) to find the square root.
My code test results are as follows
As shown in the figure above, the calculation result of my code is completely correct. However, it took 1638 milliseconds. It is still the case after many tests.
The test results of the square root method are as follows
As shown in the figure above, this method is more scientific and faster. It takes multiple tests, and it takes between 1150 milliseconds to 1250 milliseconds. Compared to my code performance, it is about 25%.
I also judge whether the digits are even or 5, and whether the sum can be divided by 3, which has been a long time. I definitely hope to reduce the amount of operations. But these codes themselves also have the amount of operations. I will remove all my code and then look at it.
The performance has been improved again. It seems that all my calculations are negatively optimized!
Finally, the code is as follows:
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){return num == ~~num ? true : false;}function isNum(num){return num == +num ? true : false;}Summary: It was entirely because of my poor arithmetic that led me to be smart in the front. However, practicing small techniques is also good -_-|||
Finally, let’s take a look at how long it takes to calculate all prime numbers within 1 million
The above is a summary of the methods for judging whether a number is a prime number introduced by the editor. I hope it will be helpful to everyone.