Procurar
Últimos assuntos
Quem está conectado?
Há 1 usuário online :: 0 registrados, 0 invisíveis e 1 visitante Nenhum
[ Ver toda a lista ]
O recorde de usuários online foi de 192 em Ter Out 26, 2021 6:07 am
Crivo de Eratóstenes (números primos)
Página 1 de 1
Crivo de Eratóstenes (números primos)
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
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;
}
juk- Mensagens : 262
Data de inscrição : 02/04/2012
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos
Seg Jan 02, 2023 2:13 pm por juk
» Cypecad 2019
Seg Jan 02, 2023 1:41 pm por juk
» Atualizando é instalando o IExplorer 11 no windows 7
Ter Ago 30, 2022 10:54 pm por juk
» COMO HABILITAR INTERNET EXPLORER NO WINDOWS 10
Sex Abr 29, 2022 6:43 pm por juk
» Usando o Monitor de Recursos do sistema para identificar processos Associados.
Qua Abr 06, 2022 10:19 am por juk
» Fazendo backup do anydesk
Ter Abr 05, 2022 7:30 pm por juk
» Recuperando Favoritos, senhas apos formatar o navegador (Mozilla Firefox ou Chrome)
Ter Abr 05, 2022 7:28 pm por juk
» Comando para tentar recuperar o windows
Qua Out 27, 2021 5:52 pm por juk
» NGROK para divulgação de site remoto
Ter Set 29, 2020 9:40 am por juk