A tatuagem do programador

Se fosse obrigatório fazer tatuagem, ao invés de tatuar aquelas asneiras de jogador de futebol, todo programador deveria tatuar seu algoritmo preferido.

tattoo

Este seria o meu, tal é a beleza e simplicidade do algoritmo concebido por Euclides para achar o máximo divisor comum entre os números inteiros x e y.

O mestre Donald Knuth diz no volume 2 da bíblia:

“[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day.”

E qual o algoritmo que você tatuaria?

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.