Prime Number Algorithm

function isPrime(n) {

// If n is less than 2 or not an integer then by definition cannot be prime. if (n < 2) {return false} if (n != Math.round(n)) {return false}

// Now assume that n is prime, we will try to prove that it is not. var isPrime = true;

// Now check every whole number from 2 to the square root of n. If any of these divides n exactly, n cannot be prime. for (var i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) {isPrime = false} }

// Finally return whether n is prime or not. return isPrime;

}

This is an algorithm I found on the internet. However, why do we sqrt(n) in the loop? couldn't I simply change that statement to "i < n (input value)" ?

• Have a look at this (but note that the title of the question is wrong, it is corrected in the answers). It shows that checking up to $\sqrt n$ is enough. Of course you can keep checking further, but it adds nothing and is just a waste of time. Commented Jul 31, 2015 at 7:42
• as Ofir Schnabel said, think why you dont need to check if 10 for example does not have any factors greater than 3? or 100 does not have any factors greater than 10? Commented Jul 31, 2015 at 7:43

You can, but why let your computer "run" to bigger numbers, if running to $\sqrt{n}$ is enough?
If $n$ is not a prime then $n$ admits a prime factor $p\leq \sqrt{n}$.
• If $n$ is not a prime with $p$ its smallest prime factor then $n\geq p^2$, namely, $p\leq \sqrt{n}$. Commented Jul 31, 2015 at 9:48