Function to check if number is prime in JavaScript

Question

Function to check if number is prime in JavaScript

Navigation

#1 by (10 votes)
#2 by (4 votes)
#3 by (2 votes)
#4 by (2 votes)

4

In PHP I would use:

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

What is the function to do the verification using JS?

javascript

asked by anonymous 09.04.2015 / 04:14

4 answers

Error creating a MySQL database via PHP in WampServer Get the value of the selected item in a ComboBox in classic asp

score 10 · Answer 1

If the number is relatively small, you can do this by simply testing whether it has divisors, such as suggested by bigown

a>. Otherwise, this solution is getting more and more 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 Test AKS - able to return "yes" or "no" with 100% of certainty and polynomial time in relation to the size of the number - but the most common in practical uses is the Miller-Rabin Test a probabilistic algorithm that returns "no" with 100% certainty or "yes" with X % sure, being X configurable (and whose execution time depends on the X chosen, tending towards infinity).

There is an example of implementing this algorithm in JavaScript on the rosettacode site (as well as implementations in several other languages) . Note that this implementation is pretty naive, so it fails even for very small numbers (the power module n is implemented power first, module later ...).

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 this you probably will also need an arbitrary precision integer library ( bigint ) - since the type Number JavaScript only supports 64-bit floating point. Here's an implementation example with this feature , for the node.js (but probably adaptable to the browser as well).

score 4 · Answer 2

According to this answer in SO you can do this:

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

document.body.innerHTML += isPrime(13);

score 2 · Answer 3

Okay okay, it's almost the same thing: in bash , and with 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 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 far from a question from the same PO }

Update 1

This response was voted negatively (at least up to -4) probably by only calculating if the number is prime until 1_299_827.

In the continuation of the "cheat alternatives" type answers, I propose the use of of the unix command primes that gives the sequence of prime numbers in a range, or the sequence of primes from a number.

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

Therefore:

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

score 2 · Answer 4

I made a slightly 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);