Um teste de primalidade é um algoritmo que responde a seguinte questão: "Dado um número inteiro positivo qualquer, esse número é primo?".
Neste artigo, apresento como responder essa pergunta utilizando o algoritmo de divisão por tentativa.

Basicamente, irei modificar um algoritmo de fatoração de uma postagem anterior do blog para que ele se torne um teste de primalidade.
Também vou disponibilizar o algoritmo codificado em Java, C e em JavaScript no final deste artigo.
Funcionamento
O funcionamento do algoritmo é idêntico ao da versão para fatoração de números. Isto é, se quisermos verificar se um número inteiro n é primo, verificamos se ele é divisível por algum inteiro menor do que n. Se ele for divisível, então n não é primo (é um número composto). Senão, n é primo.
Obviamente, os fatores não podem ser triviais. Isso significa que eles não podem ser iguais a 1 ou ao próprio n.
Otimizações
Se n é composto, então ele pode ser expresso como o produto de dois inteiros n=p×q. Consequentemente, pelo menos um dos fatores não deve ultrapassar o valor de √n, senão o produto seria maior que n [1].
Portanto, n deve ter pelo menos um fator que é menor ou igual a √n. Se p é o fator, então p2≤n. Ou seja, é suficiente procurar fatores apenas entre 2 e √n.
Além disso, para evitar redundâncias, seria interessante restringir os testes apenas aos possíveis fatores primos. Afinal, se um número é divisível por um número composto, então ele também é divisível pelos fatores primos desse composto.
Contudo, como é inviável criar uma tabela de números primos para os testes, então podemos utilizar o fato de que todo número primo, exceto 2, é ímpar para reduzir o custo pela metade.
Na prática, primeiramente verificamos se n é múltiplo de 2. Em caso negativo, verificamos se ele é múltiplo de algum número ímpar entre 3 e √n.
Uma atenção especial deve ser tomada se n=2, pois 2 é primo.
Algoritmo
A lógica apresentada nos parágrafos anteriores pode ser resumida no seguinte algoritmo:
n
é menor ou igual a 1? Se sim, entãon
não é primo.n
é múltiplo de 2 e é diferente de 2? Se sim, entãon
não é primo.n
é múltiplo de algum número ímpar entre 3 e √n? Se sim, entãon
não é primo.- Se as respostas das perguntas anteriores forem negativas, então
n
é primo.
Em bom pseudocódigo, teríamos
01. isPrime(n) //divisão por tentativa 02. | se(n ≤ 1) 03. | | retorne "n não é primo" (FALSO/NÃO) 04. | fim_se 05. | se(n = 2) 06. | | retorne "n é primo" (VERDADEIRO/SIM) 07. | fim_se 08. | se(n % 2 = 0) 09. | | retorne "n não é primo" (FALSO/NÃO) 10. | fim_se 11. | f ← 3 12. | enquanto(f2 ≤ n) 13. | | se(n % f = 0) 14. | | | retorne "n não é primo" (FALSO/NÃO) 15. | | fim_se 16. | | f ← f + 2 17. | fim_enquanto 18. | retorne "n é primo" (VERDADEIRO/SIM) 19. fim_isPrime
Complexidade assintótica
Apesar de ser um algoritmo exato, o teste de primalidade via divisão por tentativa é um algoritmo de força bruta cuja complexidade é exponencial, portanto não é recomendado para verificar a primalidade de números grandes.
O problema pode ser resolvido em tempo polinomial através do algoritmo AKS, porém a complexidade é O(log6+ϵp) [2].
Leia também
Códigos
Os códigos são apresentados a seguir.
Código em Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | //Github: HenriqueIni // Teste de primalidade "divisão por tentativa" public class TrialDivision { // Retorna true se n é primo. // Caso contrário, retorna false. public static boolean isPrime( int n){ // Casos triviais if (n <= 1 ){ return false ; } if (n == 2 ){ return true ; } // Verifica se é múltiplo de 2 if (n % 2 == 0 ){ return false ; // n é composto } // Verifica os demais fatores possíveis for ( int d = 3 ; d * d <= n; d+= 2 ){ if (n % d == 0 ){ return false ; // n é composto } } return true ; // n é primo } // Testes public static void main(String[] args) { System.out.println( "Primos até 200:" ); for ( int i = 0 ; i <= 200 ; i++){ if (isPrime(i)){ System.out.println(i); } } } } |
Código em C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | //Github: HenriqueIni #include <stdio.h> #include <stdlib.h> // Define o tipo "boolean" typedef int boolean; #define true 1 #define false 0 // Teste de primalidade "divisão por tentativa" // Retorna 'true'/1 se n é primo. // Caso contrário, retorna 'false'/0. boolean isPrime( int n){ // Casos triviais if (n <= 1){ return false ; } if (n == 2){ return true ; } // Verifica se é múltiplo de 2 if (n % 2 == 0){ return false ; // n é composto } int d; // Verifica os demais fatores possíveis for (d = 3; d * d <= n; d+=2){ if (n % d == 0){ return false ; // n é composto } } return true ; // n é primo } // Testes int main() { printf ( "Primos até 200\n" ); int i; for (i = 0; i <= 200; i++){ if (isPrime(i) == true ){ printf ( "%d\n" , i); } } return 0; } |
Código em JavaScript
O código a seguir contém apenas a função que testa se um número é primo ou composto.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | //Github: HenriqueIni // Teste de primalidade "divisão por tentativa" function isPrime(n){ // Casos triviais if (n <= 1){ return false ; } if (n == 2){ return true ; } // Verifica se é múltiplo de 2 if (n % 2 == 0){ return false ; // n é composto } var d; // Verifica os demais fatores possíveis for (d = 3; d * d <= n; d += 2){ if (n % d == 0){ return false ; // n é composto } } return true ; // n é primo } |
Referências
- [1] AMIT, ALON (23 de junho 2016). What is trial division method for factorization? How is it implemented? Is it fit for large numbers?. Acesso em 23 de abril de 2018.
- [2] WEISSTEIN, ERIC. AKS Primality Test (Wolfram Web Resource). Acesso em 26 de abril de 2018.
Nenhum comentário:
Postar um comentário