Buscar
 
 

Resultados por:
 


Rechercher Busca avançada

Últimos assuntos
Relogio

Crivo de Eratóstenes (números primos)

Ver o tópico anterior Ver o tópico seguinte Ir em baixo

Crivo de Eratóstenes (números primos)

Mensagem  juk em Qua Jan 23, 2013 12:40 pm

O Crivo de Eratóstenes é um algoritmo e um método simples e prático para encontrar números primos até um certo valor limite. Segundo a tradição, foi criado pelo matemático grego Eratóstenes (c. 285-194 a.C.).
Explicação do Algoritmo

Para exemplificá-lo, vamos determinar a lista de números entre 1 e 30.
Inicialmente, determina-se o maior número a ser checado. Ele corresponde à raiz quadrada do valor limite, arredondado para baixo. No caso, a raiz de 30, arredondada para baixo, é 5.
Crie uma lista de todos os números inteiros de 2 até o valor limite: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, e 30.
Encontre o primeiro número da lista. Ele é um número primo, 2.
Remova da lista todos os múltiplos do número primo encontrado. No nosso exemplo, a lista fica: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27 e 29.
O próximo número da lista é primo. Repita o procedimento. No caso, o próximo número da lista é 3. Removendo seus múltiplos, a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25 e 29. O próximo número, 5, também é primo; a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. 5 é o último número a ser verificado, conforme determinado inicialmente. Assim, a lista encontrada contém somente números primos.
http://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes
Código:

/* Sistemas de informação*/
/* Estruturas de Dados  */
/* Giovanni Victorette  */
/* 02/04/2005            */

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

#define TAMLISTA 25999

int main() {
   int listaPrimo[TAMLISTA];
  int i,j,k;
  int tamLP = TAMLISTA;
   int m = 0;
   int num = 2;
   long int qtd = 0;

  for (i=0; i <= TAMLISTA+1; i++) {
    listaPrimo[i] = num;
    num++;
  }

  for (i=0; i < tamLP; i++) {
    if ((listaPrimo[i]*listaPrimo[i]) > listaPrimo[tamLP-1])
      break;
    j = i + 1;
    for(k = i + 1; k < tamLP; k++) {
      qtd++;
      if ((listaPrimo[k])%(listaPrimo[i])!=0) {
            listaPrimo[j] = listaPrimo[k];
            j++;
      }
      else{
            m++;
      }
    }
      tamLP = tamLP - m;
      m = 0;
  }
  for (i=0; i < tamLP; i++)
    {
    if (listaPrimo[i] > 1) //a parti daqui comeca a conta
      {
        printf("%d",listaPrimo[i]);
      }
      getchar();
    }
printf("\nNumero de loops= %ld",qtd);
return 0;
}

Referencia vol
avatar
juk

Mensagens : 225
Data de inscrição : 02/04/2012

Ver perfil do usuário

Voltar ao Topo Ir em baixo

Ver o tópico anterior Ver o tópico seguinte Voltar ao Topo


 
Permissão deste fórum:
Você não pode responder aos tópicos neste fórum