O crivo de Eratóstenes. Um número inteiro primo é qualquer inteiro maior que 1 que pode ser dividido apenas por ele mesmo e por 1. O crivo de Eratóstenes é um método para encontrar os números primos. Ele funciona da seguinte maneira:
a) Crie um array com todos os elementos inicializados em 1 (verdadeiro). Os elementos do array com subscritos primos permanecerão em 1. Todos os outros elementos do array acabarão sendo definidos em zero.
b) Começando com o subscrito de array 2 (o subscrito 1 não é primo), toda vez que um elemento do array cujo valor seja 1 for encontrado, percorra o restante do array e defina em zero cada elemento cujo subscrito seja um múltiplo do subscrito para o elemento com valor 1. Para o subscrito de array 2, todos os elementos no array, além de 2, que sejam múltiplos de 2 serão definidos em zero (subscritos, 4, 6, 8, 10, e assim por diante). Para o subscrito de array 3, todos os elementos no array, além de 3, que são múltiplos de 3 serão definidos em zero (subscritos 6, 9, 12, 15, e assim por diante).
Quando esse processo tiver sido concluído, os elementos do array que ainda estiverem definidos em 1 indicarão que o subscrito é um número primo. Escreva um programa que use um array de 1000 elementos para determinar e exibir os números primos entre 1 e 999. Ignore o elemento 0 do array.
Passo 1
Opaaa, tudo bom? Espero que sim
Vamos inicialmente colocar a biblioteca padrão em C, depois definimos a constante size para nos auxiliar no tamanho do nosso array. Já olhando para o main, declaramos nosso vetor de tamanho size, e as demais variáveis que serão super importantes no nosso programinha.
Em seguida, já inicializamos todo o nosso array em 1(verdadeiro), em conformidade com a letra a do nosso problema.
Passo 2
Dando continuidade …
Utilizamos o laço for para percorrer todo nosso array, quando o subscrito for 0 ou 1, o valor recebido nessas posições será 0, uma vez que nem o 1 e nem o 0 são primos.
Caso sejam outros números, inicialmente os consideramos primos, por isso o 1. No entanto, é realizado um teste com a ajuda do laço for para saber se o número em questão é múltiplo de 2, 3, 5, 7, … Se forem múltiplos então aquele espaço de memória de subscrito não primo passa a ser 0.
Passo 3
Dessa forma é possível fazer a impressão dos números primos, uma vez que somente os primos possuem o valor 1. Lembrando que essa impressão ainda está dentro daquele for principal que percorre todo o array.
Bons Estudos!
Precisando estamos aqui :)
Resposta
#include
#define size 1000
int main(){
int vet[size];
int i,j,k;
int resultado = 0;
/* inicializando todos os elementos em 1 */
for(i = 0; i
vet[i] = 1;
}
for(j = 0; j
if(j == 0 || j == 1){ /* números 0 e 1 não são primos */
vet[j] = 0; /* como não são primos recebem o valor 0 */
}
else{
vet[j] = 1; /* considero inicialmente que o número é primo */
for(k = 2; k
if(j % k == 0){
vet[j] = 0; /* quando encontro os múltiplos de 2, 3, 5, 7... defino eles como 0. */
}
}
}
if(vet[j] == 1) /* imprimo os números que são primos */
printf("vet[%d]\n", j, vet[j]);
}
return 0;
}