Em PHP usaria:
for($i = 3; $i <= ceil(sqrt($num)); $i = $i + 2) {
if($num % $i == 0)
return false;
}
Qual a função para fazer a verificação usando JS?
Stack Overflow em Português é um site de perguntas e respostas para programadores profissionais e entusiastas. Leva apenas um minuto para se inscrever.
Inscreva-se para participar desta comunidadeEm PHP usaria:
for($i = 3; $i <= ceil(sqrt($num)); $i = $i + 2) {
if($num % $i == 0)
return false;
}
Qual a função para fazer a verificação usando JS?
Se o número for relativamente pequeno, dá pra fazer essa verificação simplesmente testando se ele possui divisores, como sugerido por Maniero. Caso contrário, essa solução vai ficando cada vez mais cara, até o ponto de se tornar impraticável (mesmo para números diretamente representáveis em JavaScript, sem o uso de qualquer biblioteca externa).
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/>";
Para números maiores, existe o Teste AKS - capaz de retornar "sim" ou "não" com 100% de certeza e em tempo polinomial em relação ao tamanho do número - mas o mais comum em usos práticos é o Teste de Miller-Rabin, um algoritmo probabilístico que retorna "não" com 100% de certeza ou "sim" com X% de certeza, sendo X configurável (e cujo tempo de execução depende o X escolhido, tendendo para o infinito).
Há um exemplo de implementação desse algoritmo em JavaScript no site rosettacode (bem como implementações em várias outras linguagens). Note que essa implementação é bastante ingênua, de modo que ela falha até para números muito pequenos (a potência módulo n é implementada potência primeiro, módulo depois...) .
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
E de todo modo, se você precisar de uma implementação dessas você provavelmente também precisará de uma biblioteca de inteiros de precisão arbitrária (bigint) - uma vez que o tipo Number
de JavaScript só dá suporte a ponto flutuante de 64 bits. Aqui tem um exemplo de implementação com essa característica, para o node.js (mas provavelmente adaptável para o browser também).
De acordo com essa resposta no SO dá para fazer assim:
function isPrime(number) {
var start = 2;
while (start <= Math.sqrt(number)) if (number % start++ < 1) return false;
return number > 1;
}
console.log(isPrime(13));
Eu fiz um código um pouco diferente, se quiserem dar uma olhada.
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);
Ok ok ok, é quase a mesma coisa: em bash, e com batota!
$ eprimo () { curl -s http://primes.utm.edu/lists/small/100000.txt |
grep -q -w $1 && echo "Sim" || echo "Não"; }
$ eprimo 33
Não
... mas só dá resposta se o argumento for menor que 1_299_827 e se tivermos um sistema operativo (i.e. curl, grep e coisas do género).
\cite{@bfavaretto, comentário longinquo a uma pergunta do mesmo PO}
Update 1
Esta resposta foi votada negativamente (pelo menos até -4) provavelmente por só calcular se o número é primo até 1_299_827.
Na continuação das repostas tipo "soluções alternativas com batota", proponho o uso
do comando unix primes
que dá a sequência de números primos num intervalo, ou a sequência de primos
a partir de um número.
Um número é primo se o primeiro primo a seguir a ele (primes N | head -1
)for
ele próprio! :)
Portanto:
$ perl -E '$n=shift; say((`primes $n|head -1`== $n)? "sim":"não")' 4294967231
sim