Blog do faraohh

Assuntos diversos, inclusive tecnologia.

Números primos

with 3 comments


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. Hugoprimo-hugo-m1.cprimo-hugo-m2.cprimo-hugo-m3.cprimo-hugo-m4.cprimo-hugo-m5.c

versão Marcelloprimo-marcello-m1.cprimo-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/ ]

Written by Marcello Moura

28/01/2010 às 17:48

Publicado em geral

Tagged with

3 Respostas

Subscribe to comments with RSS.

  1. Veja video sobre os 15 primeiros primos em http://www.youtube.com/watch?v=ZLorvAkyMA0

    Rogerio

    24/07/2011 at 21:22

    • É uma pena, só funciona até o 47. :-) Realmente o difícil é encontrar um padrão que até hoje não existe, senã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 at 9:43

  2. […] Anteriormente, divulgamos alguns testes com números primos para exercitar e entender um pouco de análise assintótica. Recebi um pedido de divulgação do livro “Os Fantásticos Números Primos”  de Ricardo José da Silva, ainda não o li mas fica a dica. Acompanhe a divulgação abaixo: […]


Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: