Following Wikipedia. the Naive method is:
The simplest primality test is as follows: Given an input number n, check whether any integer m from 2 to n − 1 evenly divides n (the division leaves no remainder). If n is divisible by any m then n is composite, otherwise it is prime.
For example, to test whether 17 is prime, test whether 17 is divisible by 2, or 3, or 4, 5, 6, ... , 16. Since a prime is only divisible by 1 and itself, if we reach 16 without finding a divisor, then we have proven that 17 is prime. However, we don't actually have to check all numbers up to n. Let's look at another example: all the divisors of 100:
2, 4, 5, 10, 20, 25, 50
here we see that the largest factor is 100/2 = 50. This is true for all n: all divisors are less than or equal to n/2.
We can do better though. If we take a closer look at the divisors, we will see that some of them are redundant. If we write the list differently: 100 = 2*50 = 4*25 = 5*20 = 10*10 = 20*5 = 25*4 = 50*2 it becomes obvious.
Once we reach 10, which is √100, the divisors just flip around repeat. Therefore we can further eliminate testing divisors greater than . We can also eliminate all the even numbers greater than 2, since if an even number can divide n, so can 2.
So, based on this method. We have an implementation called isPrime(numb) function
/** Check if a number is prime*/
function isPrime(numb){
for(var i=2; i<= Math.sqrt(numb); i++){
if(numb%i ==0){
return false;
}
}
return true;
}
You can see in the isPrime function. We checked the remainder from each division in which numb is dividend by a number have value from 2 to √numb.If remainder equals 0, we can break the loop, and return false (numb is not a prime).
In Javascript, We have Math built-in Object. I used Math.sqrt method to calculate value of √numb.
Speed up isPrime method
My friend +Huy Vu Quoc suggested an idea to speed up isPrime function that I mention above.
If the number we need to check is not divisible for 2, it's not divisible for any even number.So, We just need to check number 2 and all odd numbers from 2 to √numb. Our isPrime function will be the followings:
/** Check if a number is prime*/
function isPrime(numb){
if(numb%2==0) return false;
for(var i=3; i<= Math.sqrt(numb); i=i+2){
if(numb%i ==0){
return false;
}
}
return true;
}
Is it faster than before?
To known the how the performance is improve, Thank for Mr +Sudaraka Wijesinghe who has tested this script by generating 100.000 prime numbers, and using time command in Linux time ./script_name.He said:
