Teste de primalidade via divisão por tentativa

Por
|  

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.

Teste de primalidade via 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

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


Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário