Warning! Isto não é ficção.

Acabara de provar o Algoritmo da Divisão. Olhou pro quadro maravilhado. Contemplou o seu resultado por quase um minuto. Então, virou para os seus alunos. E disse:

Naquela época as pessoas não usavam roupas. Roupas eram caras, era privilégio da nobreza. Sempre que eu provo este resultado eu imagino Euclides provando-o e correndo aos seus amigos contar: “Descobri o Algoritmo da Divisão! Descobri o Algoritmo da Divisão!” e todos ficando excitados com a descoberta.

A turma do Bacharelado em Matemática Pura, assustada, fingiu que não ouviu. E de repente percebeu pela primeira vez que é compreensível o povo achar que matemática é coisa de gente maluca…

Um grande professor de Álgebra Linear, num momento muito inspirado, certa vez disse à minha turma que matrizes são como mulheres. Afinal, (sic) pode-se fazer tudo com elas: somar, subtrair, multiplicar e mais uma porção de coisas.

No início desta semana reassisti Uma mente brilhante e lembrei-me dele. Num dos lances mais interessantes do filme, John Nash de certa forma coloca as mulheres numa matriz de payoffs afim de desenvolver o Equilíbrio de Nash.

Genial.

Warning: Infelizmente o que relatarei nesta série de posts não são piadas. São diálogos que realmente aconteceram nas redondezas da Cidade Universitária.

Dois futuros engenheiros estavam estudando para a primeira prova de Cálculo I:

— O que eu ainda não entendi é o que significa uma função ser limitada — perguntou o primeiro politécnico ao seu colega inteligente.

— Isso é fácil. — responde o segundo, cheio de moral — A função é limitada quando ela tem limite.

Dica: O Programa Avançado de Matemática é um honors course de Cálculo e Álgebra Linear, com 15-20 vagas por ano, aberto a todos os alunos das áreas de ciências exatas da UFSC. Os alunos do PAM são hoje avidamente disputados por diversos grupos de pesquisa das engenharias e da matemática para trabalharem junto a laboratórios ou projetos de pesquisa.

Se tiver interesse em participar, entre em contato com o professor Mário César Zambaldi, do Depto. de Matemática.

Acredite: é provavelmente a coisa mais legal que você pode fazer ao entrar no Bacharelado em Ciência da Computação da UFSC.

Encontrar números primos é um problema comum em olimpíadas e maratonas de programação. Até hoje não existe uma maneira fácil de determinar se um número é ou não primo, mas para resolver estes problemas é indispensável o conhecimento de alguns algoritmos clássicos e simples, como o Crivo de Eratóstenes.

O Crivo de Eratóstenes é um método bastante prático para encontrar os primos de 2 até um valor limite, que pode ser feito a mão e é fácil de implementar.

O algoritmo consiste em:

1. Determinar (ou receber na entrada do programa) o valor limite, isto é, o maior número que desejamos saber se é primo.
2. Fazer a raiz quadrada do valor limite. Pode-se arredondar para baixo caso a raiz não seja exata (e quase nunca é).
3. Criar um vetor (lista) com os números de 2 até o valor limite.
4. Para i=2 até raiz do valor limite, caso o número (i) não esteja riscado insira-o na lista dos primos (ou imprima-o, ou não faça nada, isso depende da utilidade que você quer dar para o crivo) e risque todos os seus múltiplos na lista.

Há várias maneiras de implementar este algoritmo. Eu pseudocodaria (meu pseudocódigo é bem próximo de uma linguagem normal, porque acho que assim é mais fácil de entender e depois implementar) ele assim:

/_ Primeiro passo _/
recebe valorLimite

/_ Segundo passo _/
raiz $\leftarrow$ $\sqrt{valorLimite}$

/_ Terceiro passo /
para _i $\leftarrow$ 2 até valorLimite
 vetor[i] $\leftarrow$ i
fim-para

/_ Quarto passo /
para _i $\leftarrow$ 2 até raiz
 se vetor[i] = i
  imprima “O número ” i ” é primo.”
  para j $\leftarrow$ i+i até valorLimite, de i e i
   vetor[j] $\leftarrow$ 0
  fim-para
 fim-se
fim-para

Vêem como é simples?

Crivo de Eratóstenes implementado em C

#include <stdio.h>
#include <math.h> // necessário para raiz

#define NMAX 1000000 // valor máximo para o valor máximo

int main() {
    int i, j, vetor[NMAX];
    int valorMaximo, raiz;

    // Primeiro passo
    scanf("%d", &valorMaximo);

    // Segundo passo
    raiz=sqrt(valorMaximo);

    // Terceiro passo
    for (i=2; i<=valorMaximo; i++) {
        vetor[i]=i;
    }

    // Quarto passo
    for (i=2; i<=raiz; i++) {
        if (vetor[i]==i) {
            printf("%d é primo!n", i);
            for (j=i+i; j<=valorMaximo; j+=i) {
                vetor[j]=0; // removendo da lista
            }
        }
    }

    return 0;
}

No USACO Training Program Gateway (programa de treinamento para olimpíadas dos estado-unidenses) há um problema muito interessante (Prime Palindromes) cujo objetivo é determinar palíndromos primos de X a Y. Uma das melhores situações que já encontrei para usar o Crivo e sem dúvidas é um ótimo treinamento. Além de determinar primos, você terá que determinar palíndromos e é outro ótimo exercício lógico-matemático.

Divirtam-se e qualquer dúvida usem os comentários!