Testar números primos
Números primos são números que são divisíveis apenas por 1 e por eles mesmos. Então, para testar se um número é primo, é necessário verificar se algum outro número divide ele exatamente. Este guia irá te ensinar a testar se um número é primo ou não.
Primeiro, escolha um número \(n\) que quer testar se é primo ou não.
Número \(n\) a ser testado:
Agora, vamos fazer os testes de divisibilidade. Mas não é necessário testar todos os números menores que ele. Vamos testar apenas os números primos menores que \(\sqrt{n}\).
Pense no número \(n\) como o produto de dois números, \(a\) e \(b\).
Por isso, não é necessário testar valores maiores que \(\sqrt{n}\).
\( n = a \times b \)
Considerando que \(a\) e \(b\) são diferentes de \(\sqrt{n}\), então se um deles for maior que \(\sqrt{n}\), o outro deve ser menor que \(\sqrt{n}\).Por isso, não é necessário testar valores maiores que \(\sqrt{n}\).
Se um número não divide n exatamente, então nenhum múltiplo vai dividir. Por isso, ao testar se um número é
primo, não precisamos testar divisibilidade com números compostos (números que tem outros divisores além de
1 e ele mesmo), pois eles podem ser decompostos em fatores primos. Por exemplo:
\[ 25 \div 2 = 11 \text{ com resto } 1 \implies 23 \text{ não é divisível por } 2 \]
Como 2 não divide 23, então nenhum múltiplo de 2 dividirá 23 sem resto. Por isso, não é preciso testar números compostos, assim economizamos esforço sem esquecer de nenhum divisor.
\[ 25 \div 2 = 11 \text{ com resto } 1 \implies 23 \text{ não é divisível por } 2 \]
Como 2 não divide 23, então nenhum múltiplo de 2 dividirá 23 sem resto. Por isso, não é preciso testar números compostos, assim economizamos esforço sem esquecer de nenhum divisor.
Teste de Divisibilidade
Para encontrar todos os números primos até um número \(n\), podemos usar o método chamado Crivo de Erastóstenes.
- Números primos
- Testar números coprimos
- Criptografia RSA