• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

bertolo

Algoritmo razoável para dar números primos num intervalo

11 mensagens neste tópico

#include <stdio.h>

int main(void){

int a,b,p,cont,test;

printf("Introduz o intervalo:");
if((scanf("%d %d",&a,&b))==0){
printf("ERRO\n");return 0;}
if(a>b)
{
p=a;a=b;b=p;
}
printf("Intervalo:%d a %d\n",a,b);
puts("LISTA DE PRIMOS:");
for(;a<=b;a++)
{
for(test=1,cont=0; test<=(a/2) && cont<2 ;test++)
{
if(a%test==0)
cont=cont+1;
}
if(cont<2){
if(a>1){printf("%d ",a);}}
}
puts("\n");
return 0;
}

Achei que devia fazer um programa para o armazem de codigo, depois da comunidade me ter ajudado tanto e eu ainda n ter retribuido nada.

[[]]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É o método mais usual, mas nem por sombras o mais rápido.

Seria interessante, para melhorares, tanto os teus conhecimentos, como os de quem possa vir a ler este post, pesquisares sobre o crivo de eratóstenes, e outros, fazendo um código para cada um.

Até podes depois comparar tempos.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Fiz um muito parecido. Foi o post anterior ao teu. Lá encontras informações sobre o Crivo de não sei quantas Eratohsenes ou uma coisa assim. Também encontrei sobre o crivo de Atkin.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pelo que li, costumo usar o de Atkin....

Crio um array com tamanho para armazenar a quantidade de primos que quero encontrar....

coloco no primeiro índice o valor 2, e no segundo o 3;

depois, num ciclo, percorro um indice desde 5, += 2.

Para cada valor destes, vejo no array se é divisivel por algum dos valores que lá tenho (nao verifico o 2, por isso é que o indice percorre impares, e adicionei o 3 ao array). Se não, é porque é primo, e adiciono-o ao array.

Vou fazendo isto..... Requer um pouco de memória, quando se quer numeros grandes, mas trabalha bastante rápido porque encontra submultiplos muito mais rapidamente do que analisando i++......

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não me parece que isso seja o Crivo de Atkin, penso que o que estás a usar é uma versão modificada (e mais lenta) do Crivo de Eratosthenes. O teu algoritmo verifica, para cada número ímpar, se algum dos primos já descobertos é seu divisor. O Crivo de Eratosthenes original, pelo contrário, elimina logo os múltiplos dos primos já descobertos, tornando-se desnecessário percorrer o array à procura de divisores.

Além disso, pelo que percebi do teu post o algoritmo percorre o array inteiro à procura de divisores, quando devia fazê-lo apenas até chegar à raiz quadrada do número a testar. De qualquer forma, penso que um Crivo de Eratosthenes com a pequena modificação i+=2 em vez de i++ seria mais rápido que o teu algoritmo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Humm, para eliminar logo todos os subsequentes o que varia então tem de ser a incrementação.....

fazer i++ à procura de primos é completamente estúpido, isso acho que ninguém faz....

Sim, é verdade que não preciso de percorrer todo o array, mas isso é um pormenor que nem entra para algoritmos... É outro que também se deve ter em conta independentemente do método....

Eu achei que fosse de Atkin porque, ao verificar se é multiplo de 3, 5, 7, etc é que estou a pôr imediatamente de parte os multiplos dos primos já encontrados.... de outra forma torna-se complexo demais, o código... A não ser que o objectivo seja só descobrir primos....... :\

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, é verdade que não preciso de percorrer todo o array, mas isso é um pormenor que nem entra para algoritmos... É outro que também se deve ter em conta independentemente do método....

O facto de não precisares de percorrer o array inteiro é bastante importante, porque diminuis muito o número de operações a realizar. A diferença vê-se principalmente em números grandes.

Eu achei que fosse de Atkin porque, ao verificar se é multiplo de 3, 5, 7, etc é que estou a pôr imediatamente de parte os multiplos dos primos já encontrados....

Ok, mas tens de verificar isso para cada número. Por exemplo, supondo que tens o vector de primos com os números 2, 3, 5, 7 e 9. Ao processares o 11, terias de percorrer o array inteiro (na verdade, só até à raiz quadrada de 11...) para concluir que é primo (verificar se nenhum dos números do array são divisores de 11). Pelo contrário, se usasses o crivo de Eratosthenes, saberias logo que o 11 é primo porque não teria, até aí, sido eliminado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Para eliminar os números adiante, tu tens, de qualquer das formas, de realizar cálculos..... Não estás a sugerir que eu meta os números inteiros num array.........

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O Crivo de Atkin não tem nada a ver com o que vocês estão a utilizar. O crivo de  Atkin também elimina números para a frente, quadrados de números principalmente.

E juntamente com isso, acha o resto da divisão por 60 para calcular se o número é primo ou não.

http://en.wikipedia.org/wiki/Sieve_of_atkin

----

Ndray, está provado que o crivo de Eratóstenes é mais rápido do que esse teu método para encontrar primos num intervalo. Isto já foi discutido algures na secção de Algoritmia.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora