Teste de primalidade via divisão por tentativa

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\times q$. Consequentemente, pelo menos um dos fatores não deve ultrapassar o valor de $\sqrt{n}$, senão o produto seria maior que $n$ [1].

Portanto, $n$ deve ter pelo menos um fator que é menor ou igual a $\sqrt{n}$. Se $p$ é o fator, então $p^2\leq n$. Ou seja, é suficiente procurar fatores apenas entre $2$ e $\sqrt{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 $\sqrt{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:

1. n é menor ou igual a 1? Se sim, então n não é primo.
2. n é múltiplo de 2 e é diferente de 2? Se sim, então n não é primo.
3. n é múltiplo de algum número ímpar entre 3 e $\sqrt{n}$? Se sim, então n não é primo.
4. 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(\log^{6+\epsilon}p)$ [2].

Leia também

• Fatoração de números inteiros via divisão por tentativa
• Algoritmo de Euclides: implementações e aplicações do MDC
• Algoritmo para calcular o MMC
• Calculando números de Fibonacci com potenciação de matrizes

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.