Function to check if number is prime in Javascript

Question

In PHP would use:

for($i = 3; $i <= ceil(sqrt($num)); $i = $i + 2) {
        if($num % $i == 0)
            return false;
    }

What function to check using JS?

Answer 1

If the number is relatively small, you can do this check simply by testing if it has dividers, like suggested by Maniero. Otherwise, this solution becomes increasingly expensive, to the point of becoming impractical (even for numbers directly representable in Javascript, without the use of any external library).

    function isPrime(number) {
        var start = 2;
        while (start <= Math.sqrt(number)) {
            if (number % start++ < 1) return false;
        }
        return number > 1;
    }

var inicio = new Date();
document.body.innerHTML += 1125899839733757 + " " + isPrime(1125899839733757) + " " + (new Date() - inicio) + "ms<br/>";
inicio = new Date();
document.body.innerHTML += 1125899839733759 + " " + isPrime(1125899839733759) + " " + (new Date() - inicio) + "ms<br/>";

For larger numbers, there is the AKS test - capable of returning "yes" or "no" with 100% certainty and in polynomial time in relation to the number size - but the most common in practical uses is the Miller-Rabin test, one probabilistic algorithm that returns "no" with 100% certainty or "yes" with X% certainty, being X configurable (and whose runtime depends on the chosen X, tending to infinity).

There’s an example of implementing this algorithm in Javascript rosettacode (as well as implementations in several other languages). Note that this implementation is quite a lot ingenuous, so that it fails even for very small numbers (power module n is implemented power first, module after...) .

function probablyPrime(n, k) {
	if (n === 2 || n === 3)
		return true;
	if (n % 2 === 0 || n < 2)
		return false;
 
	// Write (n - 1) as 2^s * d
	var s = 0, d = n - 1;
	while (d % 2 === 0) {
		d /= 2;
		++s;
	}
 
	WitnessLoop: do {
		// A base between 2 and n - 2
		var x = Math.pow(2 + Math.floor(Math.random() * (n - 3)), d) % n;
 
		if (x === 1 || x === n - 1)
			continue;
 
		for (var i = s - 1; i--;) {
			x = x * x % n;
			if (x === 1)
				return false;
			if (x === n - 1)
				continue WitnessLoop;
		}
 
		return false;
	} while (--k);
 
	return true;
}

document.body.innerHTML += probablyPrime(13, 10); // 99.999905% de chance de estar correto

And anyway, if you need an implementation of these you probably also need an arbitrary accuracy integer library (bigint) - once the guy Number Javascript only supports 64-bit floating point. Here an example of implementation with this feature, for Node.js (but probably adaptable to the browser also).

Answer 2

According to this response in the OS you can do it like this:

function isPrime(number) {
    var start = 2;
    while (start <= Math.sqrt(number)) if (number % start++ < 1) return false;
    return number > 1;
}
console.log(isPrime(13));

I put in the Github for future reference.

Answer 3

I made a little different code, if you want to take a look.

let number = 3;
let primo = "O número " + number + " é primo";
let noPrimo = "O número " + number + " não é primo";
let result = noPrimo;

for (i = 2; i < number; i++) {
	result = primo;

	if (number % i == 0) {
		result = noPrimo;
		break;		
	}
}

if (number == 2) {
	result = primo;
}

console.log(result);

Answer 4

Okay okay okay, it’s almost the same thing: in bash, and cheating!

$ eprimo () { curl -s http://primes.utm.edu/lists/small/100000.txt | 
              grep -q -w $1 && echo "Sim" || echo "Não"; }

$ eprimo 33
Não

... but only answers if the argument is less than 1_299_827 and if we have an operating system (i.e. Curl, grep and the like).

---

\cite{@bfavaretto, comment away from a question from the same PO}

Update 1

This reply was voted against (at least up to -4) for only calculating whether the number is prime up to 1_299_827.

In the continuation of the "alternative solutions with cheating" responses, I propose the use of the Unix command primes which gives the sequence of prime numbers in an interval, or the sequence of primes from a number.

A number is prime if the first cousin after it (primes N | head -1)for himself! :)

Therefore:

$ perl -E '$n=shift; say((`primes $n|head -1`== $n)? "sim":"não")' 4294967231
sim