Um algoritmo de um dia : Como verificar um número primo em JavaScript

Marina Semes
Marina Semes

Siga

28 de Maio de 2020 · 7 min de leitura

é quase garantido que, em algum momento de sua codificação de educação, você será solicitado para escrever algum tipo de função que envolve números primos. É um exercício popular na codificação de campos de treinamento e às vezes até aparece em entrevistas de emprego.

o que são números primos?

um número primo é um número natural maior que 1 cujos únicos fatores são 1 e o próprio número. Ou seja, só pode ser dividido igualmente por 1 e por si mesmo.

os números naturais são inteiros positivos, como 1, 5, 201, 229999 etc. O número 0, frações, decimais e números negativos não são números naturais.

o número 5 é um número primo porque seus únicos fatores são 1 e 5. Não há outra maneira de “criar” o número 5.

o número 4 não é um número primo Porque 2 x 2 também nos dá 4.

o número 20 Não é um número primo porque 5 x 4 também nos dá 20, bem como 2 x 10.

números Primos são nunca mesmo, exceto para (2)

Uma das maneiras mais rápidas para verificar se um número é um número primo ou não é verificar se ele é um número par. Se um número pode ser dividido por 2 sem deixar um restante, ele não atende mais à definição de um número primo — um número que só pode ser dividido igualmente por 1 e por si mesmo.

em JavaScript, podemos verificar se há números pares usando o operador modulo (%).

o operador do módulo retorna o restante depois que um inteiro é dividido por outro.
por exemplo, 12% 5 retorna 2.
e 59% 5 retorna 4.

se você dividir um inteiro por 2 e o restante for 0, sabemos que o inteiro é um número par.

por exemplo 10% 2 = 0
e 2200 % 2 = 0

em JavaScript, será algo assim:
num % 2 === 0

Então, vamos começar a criar a nossa função JavaScript para verificar se um número é um número primo ou não:

function isPrime(num) {
if (num % 2 === 0) { return false;
} return true;}
//isPrime(40) gives us a False answer
//isPrime(101) gives us a True answer

Lembre-se que 2 É um número primo

A função acima, no entanto, também o estado que 2 não é um número primo, então vamos precisar reescrever nossa função. Também podemos cuidar de quaisquer outros inteiros que não sejam números inteiros, como 0 e números negativos.

function isPrime(num) {
if (num === 2) return true;
if (num <= 1) return false; if (num % 2 === 0) {
return false;
}
return true;
}//isPrime(0.5) gives us a False answer
//isPrime(2) gives us a True answer
//isPrime(577) gives us a True answer

a palavra-chave ‘return’ sinaliza uma saída da função quando encontra uma declaração que é verdadeira. Se o número for 2, a função para de funcionar na segunda linha:

if (num === 2) return true;

você pode encontrar uma grande lista de números primos conhecidos aqui para ajudá-lo a verificar a função.
Nem todos os números ímpares são números primos

Esta função funciona bem para verificar se um número é par ou não, mas falha com números ímpares, tais como a 9 e 27 que não são números primos.

vamos ter que verificar se o parâmetro pode ser dividido em outros fatores (exceto 1, em si e 2) sem deixar um restante. O número 9, por exemplo, também pode ser dividido por 3.

fazemos isso fazendo uso de um loop for onde a cada iteração, o parâmetro é dividido por outra variável de loop. O loop continua em execução até que não haja restos ou não haja mais variáveis de loop disponíveis.

function isPrime(num) {
if (num <= 1) return false;
if (num === 2) return true; for (let i= 2; i < num; i++) { //we start with 2 to weed out the even numbers if (num % i === 0) {
return false;
}
} return true;
}//isPrime(9) is False
//isPrime(11) is True
//isPrime(27) is False

a função mantém looping e verificação de restos. A cada iteração, o argumento é dividido por uma nova variável de loop e o restante é verificado. Se o restante for 0, significa que o argumento é completamente divisível por outro número diferente de si mesmo e não é um número primo.

nota lateral: Qual é a diferença entre um parâmetro e um argumento?
parâmetros são as variáveis usadas como parte da definição da função. Por exemplo, o num na função isPrime (num) é o parâmetro.

argumentos são os valores passados para a função quando ela é invocada. Por exemplo
o número 9 em isPrime(9) é o argumento.

Se há um resto, a função repete-se novamente até alcançar o limite em

 i < num

Quando a iteração final é atingido e ainda há um resto, o argumento é um número primo e a função pára.
terminamos com uma variável de loop que é um número menor que o parâmetro porque não estamos interessados em fatores maiores que o argumento.

uma demonstração rápida

vamos demonstrar isso com o número primo de 5.

function isPrime(num) {
if (num <= 1) return false;
//5 is larger than 1, so we continue with the function if (num === 2) return true;
//5 is not 2, so we continue with the function for (let i= 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;}

primeiro loop:
1. i = 2 e 2 < 5, então continuamos com o loop
2. 5% 2 dá um restante para que não saia do loop, mas continue com I++

segundo loop:
1. I = 3 e 3 < 5, então continuamos com o loop
2. 5% 3 dá um restante para que não saia do loop, mas continue com I++

terceiro loop:
1. I = 4 e 4 < 5, e chegamos ao final do loop porque 5 não é <do que 5
2. 5% 4 dá um resto. Isso significa que o número 5 é um número primo

Usando raízes quadradas com maiores números primos

números Primos rapidamente se transformar em grandes números. Isso significa que nosso loop for continua iterando da variável one loop para a próxima por várias vezes.

podemos encurtar o processo usando a raiz quadrada de um parâmetro. Uma raiz quadrada de um inteiro é o número que foi multiplicado por si mesmo para criar um produto.

a raiz quadrada de 81 é 9 Porque 9 x 9 = 81.

em vez de iterar de 2 a 80 para verificar se há restos restantes ou não, podemos apenas iterar até e incluindo 9, a raiz quadrada de 81.
9% 9 = 0, o que significa que 81 não é um número primo.Isso faz sentido porque 9 x 9 são fatores de 81, O que significa que não está em conformidade com a definição de um número primo — um número que só pode ser dividido igualmente por si mesmo e 1.

em JavaScript, você pode encontrar a raiz quadrada de um número usando matemática.Praca. Nós escrevemos assim:

Math.sqrt(num);

vamos usá – lo em nossa função que verifica se um número é um número primo:

function isPrime(num) {
if (num <= 1) return false;
if (num=== 2) return true; let num2 = Math.sqrt(num);//num2 is the square root of num for (let i= 2; i <= num2; i++) { //note that we are working now with the square root if (num2 % i === 0) { return false;
}
}
return true; }isPrime(521) //is True
isPrime(9801) //is False
isPrime(13037) //is True

por que os números primos são tão úteis?Em contato, O Livro de ficção científica de Carl Sagan, aliens enviar uma longa seqüência de números primos como prova de que sua mensagem é de uma força de vida inteligente. Não estamos (ainda) nos comunicando com extraterrestres por meio de números primos, mas os usamos de várias maneiras aqui no planeta Terra.

cigarras emergem em sincronia em ciclos exatos de números primos. Os ciclos irregulares significam que nenhum predador evoluiu para viver desses insetos. Além disso, o fato de que todos eles emergem do solo no momento aumenta a chance de sobrevivência de um indivíduo.As telas usam números primos para definir intensidades de cores de pixels. Eles também são usados na fabricação de ferramentas para se livrar das harmonias. Duas engrenagens que compartilham um múltiplo engatam os mesmos dentes repetidamente, o que leva a um padrão de desgaste desigual. As engrenagens que têm um número primo de dentes em suas engrenagens durarão mais.

os números primos são, no entanto, principalmente na segurança moderna do computador. Não é tão difícil encontrar grandes números primos, mas é muito difícil fatorar grandes números em números primos.

é fácil descobrir que 27 é 3 x 3 x 3, mas é muito mais difícil descobrir que 2.244.354 é 2 x 3 x 7 x 53.437. E 2.244.354 não é um número tão grande. Encontrar os fatores primos é tecnicamente uma questão de tempo, mas porque vai demorar tanto, dizemos que não pode ser feito.

algoritmos de criptografia modernos usam o fato de que ainda não existe um computador que possa pegar um número super grande e descobrir rapidamente quais primos foram para fazê-lo.

você pode estar comprando on-line ou enviando uma mensagem criptografada através de um aplicativo em seu telefone, mas em algum lugar, de alguma forma os números primos estão ajudando você a manter seus segredos seguros.

Aqui estão mais três links para outros artigos” um algoritmo por dia”:

Deixe uma resposta

O seu endereço de email não será publicado.