Verificador de número primo [C/C++]

Verificador de número primo

Publicado por White Hawk (última atualização em 10/02/2011)

[ Hits: 11.846 ]

Download 4902.primo.c

0 0

Denuncie Favoritos Indicar

Este é um script em C que pede ao usuário que digite um número e informa se ele é primo ou não.

Esconder código-fonte

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

main() {
  int num, i, cont;
  printf("============Primo============\n\n");
  printf("Digite um numero.:");
  scanf("%d", &num);
  i = 2;
  cont = 0;
    while (i < num) {
      if (num % i == 0) {
        cont++;
                
      }
      
      i++;       
    
    }
    
    if (cont > 0) {
      printf("\nO numero digitado nao e primo.");         
    
    }
    
    else {
      printf("\nO numero digitado e primo.");     
    
    }
    
    printf("\n\n");
    system("pause");       

}

Scripts recomendados

Lendo arquivos de Texto no C#

Números primos

Árvore binária de busca, algoritmos de inserção, caminhamento e busca explicados

bolinha que rebate nas bordas da janela (com SDL)

janelinha para executar comandos com system(), C/GTK

Comentários

[1] Comentário enviado por berr em 10/02/2011 - 16:53h

o maior número que divide um número, é sua raiz quadrada, por isso podes iterar meno vezes
tu já testasses que o número não é par, por isso não precisa testar nenhum outro número divisível por 2

fica mais ou menos assim:

#include <math.h>
#include <stdio.h>

int primo(int numero)
{
int i = 3;

float raiz = sqrt(numero);

// 2 e o unico numero par primo
if(numero == 2)
return 1

// outros numeros pares nao sao primos
if ((numero%2) == 0)
return 0;

// preguica de pensar, talvez itere mais do que o necessario
while (i < raiz +1) {
if((numero%i)==0)
return 0
i+= 2 // proximo numero impar
}

return 1
}

0 0

[2] Comentário enviado por f_Candido em 11/02/2011 - 23:41h

Opa,

Discordo. O maior número que divide um número, não é sua raiz quadrada, vejamos:
sqrt(16) = 4
Entretanto, 16 é divisível por 8, logo refuta sua afirmação!

Abraços

0 0

[3] Comentário enviado por WhiteHawk em 12/02/2011 - 21:50h

Olá. Realmente esse meu script pode ficar ainda mais otimizado. Como? Vejamos: todo número é divisível por 1 e por ele mesmo, porém o maior divisor de um número é a sua metade, portanto na linha while(i < num) pode ser trocada por while(i < (num/2)).

0 0