Como saber se um número é primo, saiba tudo neste  artigo continue a ler  e verifique mais detalhes.

Os números primos são números divisíveis apenas por eles próprios e por 1; todos os outros números são chamados de números compostos. Existem muitas maneiras de determinar se um número é primo.

 Alguns dos métodos são relativamente simples, mas não são adequados para grandes números. Outras técnicas que funcionam para grandes números são, na verdade, algoritmos probabilísticos que às vezes caracterizam erroneamente um número como primo ou composto.

Como saber se um número é primo

Número primo - Wikipedia, la enciclopedia libre

Como saber se um número é primo- Iterar sobre divisores é a maneira mais fácil de determinar o primo de um número. No caso de números pequenos, provavelmente esta também é a maneira mais rápida. Baseia-se na definição de um número primo: um número é primo se não tiver divisores além de si mesmo e um.

  1. 1 Seja n o número a ser verificado. De acordo com este método, você deve dividir o número n por todos os divisores inteiros possíveis. Para grandes valores de n, por exemplo, n = 101, verificar cada divisor demorará muito. Mas existem maneiras de reduzir o número de divisores a serem verificados.
  2. 2 Determine se n é par. Qualquer número par é divisível por 2. Se o número n for par, você pode declarar imediatamente que não é primo (ou seja, é um número composto). Para determinar rapidamente a uniformidade de um número, preste atenção em seu último dígito. Se o último dígito for 2, 4, 6, 8,0, então o número é par e não primo.
  3. A única exceção a essa regra é o número 2. Como ele é divisível apenas por si mesmo e por 1, o número 2 é um número primo. Assim, o número 2 é o único número primo par.
  4. 3 Divida n por cada número de 2 a n-1. Visto que o divisor é menor que o divisor, verificar todos os divisores menores que n e maiores que 2 deve mostrar se n é um número primo. Você começa com um número maior que 2 porque os números pares (que são múltiplos de 2) não são números primos. Essa está longe de ser a maneira mais eficiente de testar números para simplificar, mas existem vários métodos para otimizar a validação.
  5. Por exemplo, vamos verificar o número 11. Neste caso, dividimos 11 (inteiramente) por 3, 4, 5, 6, 7, 8, 9, 10. Como nenhum desses números divide (inteiramente) 11, o número 11 é um número primo.
  6. 4 Para economizar tempo, verifique os fatores para a raiz quadrada arredondada (n). Verificar todos os divisores de 2 a n-1 pode levar muito tempo. Por exemplo, se você quiser testar o número 103, terá que testar os seguintes divisores: 3, 4, 5, 6, 7. e assim por diante até 102! Mas isso pode ser evitado – verifique apenas os divisores de 2 ao valor da raiz quadrada arredondada (n).
  7. Explicação deste princípio. Considere os fatores de 100,100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2, 100 × 1. Observe que após um par de fatores 10 × 10 todos os pares de fatores são repetidos (apenas os fatores nesses pares são trocados). Portanto, você pode ignorar n divisores maiores que a raiz quadrada (n).
  8. Por exemplo, vamos testar n = 37. Você não precisa testar todos os divisores de 3 a 36. Em vez disso, teste os divisores entre 2 e a raiz quadrada arredondada (37).
  9. Raiz quadrada (37) = 6,08. Arredonde esse número para 7.
  10. 37 não é divisível por 3, 4, 5, 6, 7, por isso é simples.
  11. 5 Para economizar ainda mais tempo, teste apenas os fatores primos. Por definição, qualquer número composto pode ser expresso como o produto de dois ou mais números primos. Portanto, dividir n por um divisor composto é uma operação desnecessária que repete a divisão múltipla de n por fatores primos. Assim, você pode restringir ainda mais o número de divisores em teste.
  12. Isso significa que todos os divisores pares e todos os divisores que são múltiplos de números primos podem ser omitidos.
  13. Por exemplo, vamos verificar o número 103. A raiz quadrada de 103 é arredondada para 11. Os fatores primos de 2 a 11 são 3, 5, 7, 11. Os fatores 4, 6, 8, 9, 10 podem ser omitidos ( 9 é um múltiplo de 3 e todos os outros fatores – números pares). Assim, você reduziu o número de divisores a serem testados para quatro números.
  14. Os divisores 3, 5, 7, 11 não dividem (completamente) 103, por isso é primo.

Método 2 Test Farm

Em 1640, o matemático francês Pierre Fermat formulou pela primeira vez um teorema (o pequeno teorema de Fermat), que é usado para determinar o primo de um número. Na verdade, o teste de Fermat é usado para determinar números compostos, não primos. Este teste determina com confiança se um número é composto ou se um número é “provável” ser primo. O teste de Fermat é útil nos casos em que iterar sobre divisores é impraticável e quando uma lista de números que são exceções ao teorema está disponível.

  1. 1 Seja n o número a ser verificado. Conforme observado acima, às vezes o teste identifica falsamente os números compostos como primos. Portanto, é necessário verificar a resposta (o método de verificação da resposta está descrito a seguir).
  2. 2 Selecione qualquer número inteiro “a” entre 2 e n-1 (inclusive).
  3. Por exemplo, vamos verificar a simplicidade do número 100. Suponha que a = 3.
  4. 3 Calcule n (mod n ). A avaliação dessa expressão exigirá algum conhecimento de aritmética modular. Na aritmética modular, quando um certo valor, chamado módulo, é alcançado, os números começam do zero. Pense nisso como um relógio: a hora depois do meio-dia é 1h, não 13h, o que significa que o tempo da tarde é contado a partir de zero. O módulo é designado como mod n. Portanto, calcule um (mod n).
  5. Uma maneira de calcular é calcular an, dividir o resultado por n e escrever o restante da divisão como uma resposta. Neste caso, recomenda-se o uso de calculadoras especializadas com função de módulo, uma vez que calculam instantaneamente o restante ao dividir grandes números.
  6. Em nosso exemplo, dividir 3 100/100 resulta em 1. Portanto, 3 100 (mod 100) = 1.
  7. 4 Se você não tiver uma calculadora especializada, ao calcular o resto manualmente, use a notação exponencial do número.
  8. Em nosso exemplo, calcule manualmente 3 100 (mod 100). 3 100 = 515377520732011331036461129765621272702107522001 é um número enorme com o qual é difícil trabalhar. Em vez de trabalhar com um número de 48 dígitos, pense em 3 100 como ((((((((3 2) * 3) 2) 2) 2) * 3) 2) 2 . Lembre-se de que ao elevar uma potência a uma potência, os indicadores são multiplicados: ((xy) z = x yz).
  9. Agora defina o restante. Em (((((((3 2) * 3) 2) 2) 2) * 3) 2) 2 comece a solução com os colchetes internos e divida o resultado por 100 a cada vez. Como uma resposta).
  10. (((((((9) * 3) 2) 2) 2) * 3) 2) 2 – 9/100 – sem resto.
  11. ((((((27) 2) 2) 2) * 3) 2) 2 – 27/100 – sem resto.
  12. (((((729) 2) 2) * 3) 2) 2 – 729/100 = 7 (resto 29). Restante 29. Continue os cálculos com o número 29.
  13. ((((29 2 = 841 ) 2) * 3) 2) 2 – 841/100 = 8 (repouso 41). Restante 41. Continue os cálculos com 41.
  14. (((41 2 = 1681 ) * 3) 2) 2 – 1681/100 = 16 (restante 81). Restante 81. Continue com 81.
  15. ((81 * 3 = 243 ) 2) 2 – 243/100 = 2 (descanso 43). Restante 43. Continue os cálculos com 43.
  16. (43 2 = 1849 ) 2 – 1849/100 = 18 (resto 49). Restante 49. Continue os cálculos com 49.
  17. 49 2 = 2401 – 2401/100 = 24 (descanso 1). O resto final é 1. Portanto, 3 100 (mod 100) = 1 (o mesmo resultado foi obtido ao calcular em uma calculadora).
  18. 5 Verifique a igualdade: n (mod n ) = a (mod n ). Se não for atendido, então n é um número composto. Se for encontrado, então n é provavelmente um número primo (mas não obrigatório). Repita o teste com diferentes valores de a para certificar-se de que a resposta está correta. Mas existem números compostos que satisfazem a condição de Fermat para quaisquer valores de “a”. Eles são chamados de números de Carmichael (o menor dos quais é 561).
  19. Em nosso exemplo, 3 100 (mod 100) = 1 e 100 (mod 100) = 0. Assim, 1 ≠ 0 e 100 é um número composto.
  20. 6 Use os números de Carmichael como garantia da resposta correta. Os números de Carmichael são da forma (6k + 1) (12k + 1) (18k + 1) para o inteiro k quando cada divisor é primo. Você pode encontrar uma lista completa dos números de Carmichael na internet.

Teste do Método 3 de Miller-Rabin

O teste de Miller-Rabin determina com eficiência se um número é composto (e lida melhor com exceções como os números de Carmichael).

  1. 1 Seja n um número ímpar a ser testado quanto à simplicidade.
  2. 2 Escreva n-1 como 2 s × d, onde d é um número ímpar. Se n for primo, então deve ser ímpar. Portanto, n-1 é par. Como n-1 é um número par, ele pode ser representado como o produto do número 2, até certo ponto, por um número ímpar. Por exemplo, 4 = 2 2 × 1, 80 = 2 4 × 5 e assim por diante.
  3. Por exemplo, defina o número primo n = 321. 321 – 1 = 320 e 320 = 2 6 × 5. Ou seja, s = 6 e d = 5.
  4. Por exemplo, pegue um número mais complexo n = 371. 371 – 1 = 370 e 370 = 2 1 × 185. Ou seja, d = 185, o que complicará muito os cálculos.
  5. 3 Pegue qualquer número “a” entre 2 e n-1.
  6. Em nosso exemplo, para n = 321, escolha a = 100.
  7. 4 Calcule d (mod n ). Se d = 1 ou -1 (mod n ), então o número n passa no teste de Miller-Rabin e é provavelmente simples. No entanto, este teste, como o teste de Fermat, não pode determinar a simplicidade de um número com certeza absoluta.
  8. Em nosso exemplo, para n = 321: ad (mod n) = 100 5 (mod 321). 100 5 = 10.000.000.000 (mod 321) = 
    313 . Para encontrar o restante de 100 5/321, use uma calculadora especializada ou cálculo manual (descrito acima).
  9. Como o resultado não é 1 ou -1, você não pode argumentar que n é um número primo.
  10. 5 Se o resultado não é igual a 1 ou -1, calcular um 2 d , uma 4 d , .. e assim por diante até a 2 s -1 d . Se um dos resultados for 1 ou -1 (mod n), então o número n passa no teste de Miller-Rabin e é provavelmente primo. Se n passar no teste, verifique sua resposta (consulte a próxima etapa). Se n falhar em qualquer um desses testes, então n é um número composto.
  11. Lembre-se de que em nosso exemplo a = 100, s = 6, d = 5. Continue verificando o seguinte:
  12. 100 2d = 10 = 1 × 10 20.
  13. 1 × 10 20 (mod 321) = 64,64  1 ou -1. Continue os cálculos.
  14. 100 4d = 20 = 1 × 10 40.
  15. 1 × 10 40 (mod 321) = 244,244  1 ou -1.
  16. Aqui você pode terminar seus cálculos. s – 1 = 6 – 1 = 5. Você atingiu o valor limite 4d = 2 2. Como nenhum dos cálculos deu 1 ou -1, você pode afirmar com segurança que n = 321 é um número composto.
  17. 6 Se n passar no teste de Miller-Rabin, repita o teste com diferentes valores de a para certificar-se de que a resposta está correta. Se n for um número primo, ele passará no teste com qualquer valor de “a”. Se n for um número composto, pelo menos três quartos dos valores “a” falharão no teste. Portanto, o teste de Miller-Rabin é mais confiável do que o teste de Fermat, no qual os números de Carmichael compostos passam no teste para qualquer valor de “a”.