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:
né menor ou igual a 1? Se sim, entãonnão é primo.né múltiplo de 2 e é diferente de 2? Se sim, entãonnão é primo.né múltiplo de algum número ímpar entre 3 e $\sqrt{n}$? Se sim, entãonnã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(\log^{6+\epsilon}p)$ [2].
Leia também
Códigos
Os códigos são apresentados a seguir.
Código em Java
//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
//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.
//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