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: