Explicação

[Guest - Deco -]

main()

{

int numero=1,divisor=1,contador=0;

while(numero<100)

{

while(divisor<=numero)

{

if((numero%divisor)==0)

{

contador++;

}

divisor++;

}

if(contador<=2)

{

printf("%d ",numero);

}

divisor=1;

contador=0;

numero++;

}

getch();

}

Sou iniciante na linguagem C, e gostaria que alguém me explicasse passo a passo esse código.

Ele exibe o números primos de 1 até 100, mas não estou conseguindo entender muito bem a lógica dele. Se alguém me explicar ficarei muito agradecido :)

[Graymalkin]

Bom, ele não mostra exatamente os números primos, porque 1 *não* é primo. Tirando isso, o que ele faz é um loop de 1 a 100 (que é o primeiro While) e cada iteração (loop) ele incrementa a variável "divisor" até chegar no número atual, e assim conta quantos divisores o número (do primeiro loop) tem. Para saber quando o número é divisível ou não é que se utiliza o operador Modulus (%) que retorna o resto da divisão. Se o resto for zero, é porque a divisão é exata, portanto o número é divisível pelo outro.

Existe uma ténica melhor para descobrir os números primos, já que o próximo primo não vai ser divisível por nenhum dos outros primos até a sua raíz quadrada. Ou seja, para saber se 29 é primo basta testar se ele não é divisível, simultaneamente, por 2, 3 e 5 (já que a raíz quadrada de 29 é 5,3851648071345). Note que só será necessário testar 3 divisores, enquanto que no seu código acima é necessário testar 29 divisores. E, economia de iterações significa maior velocidade, é claro.

Abraços,

Graymalkin

[Guest Visitante]

Entendi, mas não seria necessário fazer a verificação com o número 7 também ???

[Graymalkin]

Entendi, mas não seria necessário fazer a verificação com o número 7 também ???

Não, por quê seria? :huh: A verificação é feita com os primos menores ou iguais a raíz quadrada do número. E 7 não é menor do que 5,38.

Abraços,

Graymalkin

[Guest Visitante]

Mas eu tenho que levar em consideração a raíz de 49 ( que é 7). Já que eu estou exibindo os números primos de 0 a 100.

Estou certo ou estou fazendo confusão ??? :D

[Graymalkin]

Mas eu tenho que levar em consideração a raíz de 49 ( que é 7). Já que eu estou exibindo os números primos de 0 a 100.

Sim, mas eu citei o 29 (vinte e nove) como o *exemplo*, e não o 49. *Quando* chegar no 49, é claro, você vai incluir o 7 (até porque se você não fizer isso ele vai ser considerado primo, o que não é verdade).

Estou certo ou estou fazendo confusão ??? :D

Dê uma lida novamente no meu primeiro post para se certificar de que eu escrevi 29 (vinte e nove) e não 49.

Abraços,

Graymalkin

[Guest Visitante]

Ahh sim, já consegui resolver. Muito Obrigado!!!

[Guest ananda]

Entendi, mas não seria necessário fazer a verificação com o número 7 também ???

[Marcelo Utikawa da Fonseca]

Esta lógica de checar até os primos menores que a raiz quadrada do número em teste está errada. Vamos supor que o número em teste seja 21. Sua raiz quadrada é cerca de 4,58, ou seja, precisamos testar apenas 2 e 3 mas 21 é divisível por 7!

Assim não adianta nem mesmo utilizar até o próximo número primo além da raiz quadrada pois seria 5.

Me confundi... Seria divisível por 3 e portanto saberíamos que não é primo!

Foi mal... :)