Nesta segunda parte vamos mostrar testes que rapidamente dizem se um numero é provavelmente primo, provavelmente porque como veremos abaixo eles checam rapidamente se não é primo, mas quando dizem que é primo … Aí tem alta probabilidade de ser primo e se você quiser ter certeza precisa usar um algoritmo mais lento.
Este que vou mostrar se baseia no Pequeno Teorema de Fermat. Este teorema é bem simples de enunciar:
Se um número p é primo então para todos os números a entre 1 e p-1 a equação abaixo tem que ser respeitada (em notação C++):
pow (a,p-1) % p = 1 |
Assim fazemos o teste para alguns números a entre 1 e p-1 e caso a equação seja verdadeira para eles podemos dizer que é provavelmente primo. Se falhar para algum número não é primo com certeza.
#define NUMTESTES 10 // vamos testar 10 vezes, pode ser um número maior ... int isPrimo (int n) { if (n==1) return 0; // dica de um leitor da semana passada if (n<4) return 1; for (int i=0; i<NUMTESTES; i++) { if (i+1 > n-1) break; // aqui estou supondo que há uma biblioteca // de precisão arbitrária como a mathX // ou usando uma técnica de obter modulo // em exponenciação como a // Fast Modular Exponentiation if (pow(i+1,n-1)%p != 1) return 0; } return 1; } |
Caso o resultado seja 0 você pode estar certo de que não é primo, se for 1, você pode ter uma enorme probabilidade de ser primo.
Para algumas aplicações é preciso ter certeza que o número é primo e como existem os números de Carmichael que se comportam como primos nestes testes probabilísticos vamos ver na próxima parte como testar rapidamente e com certeza (já adianto que é bem complicado do ponto de vista matemático…)
Como sempre, se houver erros favor apontar nos comentários.