Tiago Madeira

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!

Hoje, depois de umas férias de dois meses, resolvi um problema lógico do USACO Training Gateway: o Superprime Rib é um problema bem simples em que precisa-se determinar os primos de N dígitos (com N máximo = 8 ) que, tirando o último dígito, continuam sendo primos. A solução é trivial, uma função recursiva bastante simples que se auto-explica no meu código:

//Superprime Rib - USACO Training Gateway - 2005

/*
ID: contato1
PROG: sprime
LANG: C
*/

#include <stdio.h>
#define NMAX 9
#define INFINITO 100000

int primos[NMAX][INFINITO], cont[NMAX];

int eh_primo(long int num) {
	int i;

	if (num==1||(!(num%2)&&num!=2)) {
		return 0;
	}

	for (i=3; i*i<=num; i+=2) {
		if (!(num%i)) {
			return 0;
		}
	}

	return 1;
}

void funcao(int n) {
	int i, j, num;

	cont[n]=0;

	if (n>1) {
		funcao(n-1);

		for (i=0; i<cont[n-1]; i++) {
			for (j=1; j<=9; j+=2) {
				num=primos[n-1][i]*10+j;
				if (eh_primo(num)) {
					primos[n][cont[n]++]=num;
				}
			}
		}
	} else {
		primos[1][0]=2;
		primos[1][1]=3;
		primos[1][2]=5;
		primos[1][3]=7;
		cont[1]=4;
	}
}

int main() {
	int n, i;

	FILE *in=fopen("sprime.in", "r");
	FILE *out=fopen("sprime.out", "w");
	fscanf(in, "%d", &n);
	fclose(in);

	funcao(n);

	for (i=0; i<cont[n]; i++) {
		fprintf(out, "%d\n", primos[n][i]);
	}
	fclose(out);

	return 0;
}

O problema passou de segunda porque na primeira, por falta de hábito, eu tinha colocado scanf e printf ao invés de usar o sistema da USACO onde deve-se usar arquivos de entrada e saída.

Agora para eu ir para a seção 2 do USACO Training Gateway falta só o programa Checker Challenge, que parece ser complicado.

Instalei os pacotes do Slackware 10.2, que saiu essa semana, no laptop. Não tem nenhuma grande mudança, mas é sempre bom estar com os programas atualizados…

O Paulo Matias (Thotypous) me convidou para fazer parte da equipe de desenvolvimento da distro Guaranix, consertando alguns bugs do XDirectFB (que eu citei aqui). Acho que irei pegar um trabalho com a Meetweb também (o Hugo Dias, para quem eu fiz o serviço da Coalizão Antituberculose me convidou) e estou acabando o site do Colégio Salesiano, que é totalmente administrável em PHP e usa um banco de dados MySql. Ele deve sair semana que vem…

Dia 24 é a segunda fase da Olimpíada Regional de Matemática. Essa semana fiz a folhinha de treinamento e dos seis problemas, consegui fazer cinco (na verdade, alguns problemas - ou todos - eram repetidos do ano anterior e por isso fica mais fácil, porque eu já lembrava o caminho).

Fiquei um bom tempo sem fazer o treinamento da USACO, porque há algum tempo tinha parado no programa Prime Palindromes, cujo objetivo é listar todos os palíndromos primos entre dois números (limites: 5, 10.000.000).

Esta demora aconteceu porque eu, além de ter ficado muito tempo sem entrar na USACO e já ter me esquecido do problema, estava testando todos os números, vendo se eles eram palíndromos, depois primos e então imprimia. Quando eu entrei na USACO essa semana (idéia do César Kawakami, que também vai pra UNICAMP mês que vem e foi um cara que também me ajudou nesse problema) vi que tinham Hints que eu nunca tinha visto antes. E elas diziam que eu devia gerar palíndromos. Com isso ficou fácil…

Eu ainda boiei um pouco, porque só depois eu descobri uma coisa lógica e muito simples (que eu nunca tinha pensado antes): Para descobrir se um número N qualquer é primo, basta ver se ele é divisível pelos primos (no caso, eu usei todos os números, não só primos) de 2 a raiz de N. Bom, isso é bem óbvio… Mas ninguém nunca tinha me dito e eu nunca tinha visto em lugar nenhum! Então tive que pensar (descobrir sozinho mesmo).

Por preguiça de só fazer alguns for caso o mínimo fosse menor que X e maior que Y, meu programa, para qualquer caso, pega todos os palíndromos primos de 5 a 10000000! :blink: Eu não sabia se o tempo disso ia ser suficiente, então resolvi testar assim antes de fazer esses ifs antes do for e deu certo! Logo, nem precisa mais de nada… O tempo do meu programa para qualquer teste, no meu Linux, é 0,032 segundos. Na USACO apareceu como 0,05 segundos.

Código-fonte

//Prime Palindromes - USACO Training Gateway
//Tiago Madeira (c)

//Agora eu sei que dá pra fazer com custo bem menor,
//mas esse aí rolou na boa com 0.05 segundos.

/*
ID: contato1
PROG: pprime
LANG: C
*/

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

int eh_primo(long int num) {
	int i;

	for (i=3; i*i<=num; i+=2) {
		if (!(num%i)) {
			return 0;
		}
	}

	return 1;
}

int main() {
	int i, j, k, l, cont=0;
	long int numero, min, max, v[10000];

	FILE *in=fopen("pprime.in", "r");
	FILE *out=fopen("pprime.out", "w");
	fscanf(in, "%d %d", &min, &max);
	fclose(in);

	v[cont++]=5;
	v[cont++]=7;
	for (i=1; i<=9; i+=2) {
		numero=i*10+i;
		if (eh_primo(numero)) {
			v[cont++]=numero;
		}
	}
	for (i=1; i<=9; i+=2) {
		for (j=0; j<=9; j++) {
			numero=i*100+j*10+i;
			if (eh_primo(numero)) {
				v[cont++]=numero;
			}
		}
	}
	for (i=1; i<=9; i+=2) {
		for (j=0; j<=9; j++) {
			for (k=0; k<=9; k++) {
				numero=i*10000+j*1000+k*100+j*10+i;
				if (eh_primo(numero)) {
					v[cont++]=numero;
				}
			}
		}
	}
	for (i=1; i<=9; i+=2) {
		if (i==5) {
			i=7;
		}
		for (j=0; j<=9; j++) {
			for (k=0; k<=9; k++) {
				for (l=0; l<=9; l++) {
					numero=i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i;
					if (eh_primo(numero)) {
						v[cont++]=numero;
					}
				}
			}
		}
	}
	for (i=0; i<cont; i++) {
		if (v[i]>=min&&v[i]<=max) {
			fprintf(out, "%d\n", v[i]);
		} else if (v[i]>max) {
			fclose(out);
			return 0;
		}
	}
	fclose(out);
	return 0;
}

Agora vou prosseguir com o treinamento do USACO Training Gateway na seção 1.3, a começar pelo problema Mixing Milk.

Nos últimos dias não aconteceu nada demais. Só fiquei emocionado por ter recebido um 9,1 em biologia… :lol: E outra coisa legal também é que eu reli O Homem que Calculava e achei muito legal. Eu tinha lido na sexta série e acho que não tinha entendido direito tudo. O livro é muito bom e não é muito complicado não. O próximo que eu quero reler é O Diabo dos Números. Esse é mais “avançado” que o primeiro. Tô fazendo um trabalho de escola (de história) sobre (o filósofo) Pitágoras. É bem legal, o cara era muito bom. Na verdade, o trabalho tá virando de matemática, mas é bem interessante. É legal ter um professor de história que dá aula… ;) Não é igual ano passado, né? Tô achando bem legal os períodos da Grécia Antiga.

Ah, e vou finalizar citando um trecho d’O Homem que Calculava em homenagem ao Vavá, que não respira oxigênio… :D

Conta-se que o famoso rei Salomão, para demonstrar a finura e a sabedoria de seu espírito, deu à sua noiva, a rainha de Sabá – a famosa Belquiss – uma caixa com 529 pérolas. Por que 529? Sabe-se que 529 é o quadrado de 23, isto é, 529 é igual a 23 multiplicado por 23. E 23 era, exatamente, a idade da rainha.