quarta-feira, 18 de novembro de 2009

Um passo de cada vez... Algoritmos (números primos)

Hoje vamos analisar um algoritmo para determinar se um número é primo.
Você sabe o que é um número primo? Veja aqui.
Agora que sabemos o que é um número primo, vamos ao algoritmo?
Antes, uma pequena observação: o algoritmo apresentado aqui tem como único e exclusivo objetivo ensinar o princípio do seu funcionamento, portanto, não está focado na velocidade e eficiência. Ok?
Dito isto, vamos ao código.


//PROGRAMA PARA VERIFICAR SE UM NÚMERO É PRIMO
#include <stdio.h>
#include <stdlib.h>
 
int main(){
 int num, nao_primo=0, divisoes=0, i;
 
 printf("Digite um numero inteiro: ");
 scanf("%d",&num);
 if ((num == 1) || (num % 2 == 0) && (num != 2))
    nao_primo = 1;
 else
    for(i = 1; (i <= num) && (divisoes <= 2); i += 2){
       if (num % i == 0)
          divisoes++;
    }
 if ((nao_primo == 0) && (divisoes <= 2))
    printf("O numero %d eh primo!\n",num);
 else
    printf("O numero %d nao eh primo!\n",num);
 system("pause");
}


Na linha 10 verificamos se o número digitado é 1 ou se é um número par diferente de 2. Se for, já sabemos, por definição, que não é um número primo, e informamos isto na linha 11.
Se o número digitado não se encaixar em nenhuma das opções anteriores, iremos testar, usando um comando de repetição for (linha 13), a quantidade de divisões exatas do número pelos números ímpares de 1 até o próprio número. A cada divisão exata incrementamos uma variável divisoes na linha 15. Se houverem mais de duas divisões exatas nem precisamos continuar testando, pois um número primo só é divisível por 1 e por ele mesmo, ou seja, duas divisões exatas.
Observou a forma que usamos para fazer a divisão somente pelos números ímpares? Incrementando a variável i que controla a quantidade de repetições do for de 2 em 2 (i += 2). Inteligente, não?
As outras linhas do código são apenas para informar se o número é primo ou não.
Viu como um código que parecia difícil, se tornou fácil?

Está gostando do blog? Comente, marque sua opinião nas reações abaixo, seja um seguidor do blog, siga o nosso twitter... Sua opinião é importante para sabermos se estamos no caminho certo, que é tornar o C mais fácil.
Até a próxima.

14 comentários:

  1. Mto bom seu blog!!!
    Ta me ajudando bastante!!

    Brigada!

    ResponderExcluir
  2. vlww brother muito bomm!

    ResponderExcluir
  3. muuuuito massa parabéns!!!! vlw msm...

    ResponderExcluir
  4. Muito bom,Parabens... Abraço. Você é fera.

    ResponderExcluir
  5. Legal mas o numero é primo.
    E 2 tambem é primo
    Mas bem legal o programa

    ResponderExcluir
  6. muito legal... me ajudou bastante!!! obg..

    ResponderExcluir
  7. esse algoritmo e muito foda

    ResponderExcluir
  8. Muito bom, mas há falhas.
    Se digitar qualquer múltiplo de 3, 5 ou 7 diz que é primo.
    Tem que colocar essas restrições no primeiro if-else, como você fez com o número 2.

    ResponderExcluir
  9. Adorei!

    me salvou! valeu

    ResponderExcluir
  10. Este comentário foi removido pelo autor.

    ResponderExcluir
  11. Olá, tenho uma dúvida.
    Fiz o teste e funcionou corretamente, mas quero saber como faço para sempre repetir a pergunta?

    ResponderExcluir