Números primos
Introdução
Começamos com uma versão básica de um programa em C que computa a quantidade de números primos entre 2 e um dado N. Logo criamos uma tabela para analisar o desempenho desse algoritmos e implementamos algumas melhorias gradativas.
Implementação em C
Os algoritmos criados foram:
versão básica: primo-v1.c
versão Prof. Hugo: primo-hugo-m1.c, primo-hugo-m2.c, primo-hugo-m3.c, primo-hugo-m4.c, primo-hugo-m5.c
versão Marcello: primo-marcello-m1.c, primo-marcello-m2.c
O algoritmo primo-hugo-m5.c foi implementado com Threads fazendo uso de 1 ou mais núcleos de processamento, podendo reduzir o tempo para se computar a quantidade de primos.
A Tabela de comparações
As comparações foram feitas usando o comando time em uma estação GNU/Linux/Debian com processador Intel Core 2 Duo com 2 GB RAM.
| Algoritmo | 102 (25) | 103 (168) | 104 (1229) | 105 (9592) | 106 (78498) | 107 (664579) |
|---|---|---|---|---|---|---|
| primo-v1.c | 0m0.001s | 0m0.002s | 0m0.035s | 0m3.223s | 3m42.381s | |
| primo-hugo-m1.c | 0m0.001s | 0m0.002s | 0m0.035s | 0m3.265s | 3m41.540s | |
| primo-hugo-m2.c | 0m0.001s | 0m0.001s | 0m0.019s | 0m1.737s | 2m0.725s | |
| primo-hugo-m3.c | 0m0.001s | 0m0.001s | 0m0.010s | 0m0.875s | 1m0.960s | |
| primo-hugo-m4.c | 0m0.001s | 0m0.001s | 0m0.002s | 0m0.020s | 0m0.404s | 0m8.949s |
| primo-marcello-m1.c | 0m0.001s | 0m0.001s | 0m0.003s | 0m0.035s | 0m0.784s | 0m17.592s |
| primo-marcello-m2.c | 0m0.001s | 0m0.001s | 0m0.002s | 0m0.021s | 0m0.410s | 0m8.989s |
Licença de Uso
Os códigos está sob GPL e artigo está sob licença CC, conforme informações abaixo.
Artigo sob a Licença Creative Commons [ http://creativecommons.org/licenses/by/3.0/ ]
Veja video sobre os 15 primeiros primos em http://www.youtube.com/watch?v=ZLorvAkyMA0
Rogerio
24/07/2011 em 21:22
É uma pena, só funciona até o 47. :-) Realmente o difícil é encontrar um padrão que até hoje não existe, a não o teorema que diz que: precisamos buscar um divisor desse número até a sua raiz quadrada se não existe ele é primo. Isso melhora o algoritmo mas não o necessário para baixar sua complexidade. Mais informações em [0].
[0] http://en.wikipedia.org/wiki/Trial_division
Abraços.
Marcello Henrique
25/07/2011 em 9:43