Números primos e algoritmos – Parte I

Um dos fundamentos da criptografia e dos sistemas de assinatura digital são os números primos. O princípio que rege a criptografia assimétrica (RSA) é o fato de ser rápido descobrir se um número é primo e é lento fatorar um número.

O RSA fica para outro post, agora queria focar na pergunta: como faz para saber se um número é primo?

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i < x; i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Obviamente esta função não é a melhor, ela roda em O(n) ou seja o tempo de execução cresce linearmente com o tamanho do número em questão.

Uma otimização que alguns alunos espertos no curso de Computação I fazem é a seguinte:

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i =< x/2; i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Isto diminui o tempo de execução pela metade mas não muda a complexidade do algoritmo, ela continua sendo O(n). Portanto para números grandes isto não ajuda muito.

Uma coisa que podemos usar para melhorar a complexidade (ainda não ajuda muito, mas hoje paramos por aqui) é o fato de que se um número não tem nenhum divisor menor que a raiz quadrada dele ele não tem nenhum divisor (a prova disto é fácil e fica como exercício para o leitor 🙂 )

int isPrimo (int x) {
   if (x < 4) return 1;
   for (int i=0; i =< sqrt(x); i++) {
      if (x%i == 0) return 0;
   }
   return 1;
}

Neste caso a complexidade que era O(n) passa a ser O(√n)

Melhorou? Sim. Mas ainda não é o suficiente. No próximo capítulo desta série, veremos métodos que dizem se um número é provavelmente primo.

Se você achar algum erro nos códigos acima, comente.

Comments on this entry are closed.

  • É isso ai PP, recordei agora quando lidava com desenvolvimento, saudade daqueles compiladores mais simples do tipo BASIC, depois VB e DELPHI. Força e Honra irmão!

  • dclobato

    Na realidade não é um erro, mas uma observação: o valor de sqrt(x) não muda a cada iteração. Assim, entre o if e o for da última listagem, poderia ter um “y = sqrt(x)”, e o limite do for vai até y. Não muda a complexidade do algoritmo, mas reduz o tempo… 🙂

  • Pedro Paulo

    @dclobato. Poderia fazer isto, mas os compiladores otimizam isto e o código fonte fica menor. De qualquer forma obrigado pela dica.

  • 1 não é primo, mas passa o seu teste.

  • Pedro Paulo

    @gleison, você tem razão. Vou deixar assim por enquanto e conserto isto no post da semana que vem.

  • marcio

    O primeiro algoritmo é da ordem de n^2 e não linear. O dia em que você definir um algoritmo de ordem linear para decidir se um número é primo, prepare-se para ganhar muito dinheiro.