Saber se um número é primo (algoritmo super simples) [C/C++]

Saber se um número é primo (algoritmo super simples)

Publicado por Francisco Leandro Xavier Carneiro (última atualização em 24/05/2010)

[ Hits: 241.143 ]

Homepage: http://conexaotech.blogspot.com/

Download 4595.primo.c

17 0

Denuncie Favoritos Indicar

Algoritmo para saber um número (lido pelo programa) é primo ou não...

Esconder código-fonte

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

int main() {
  
  int i, x; 
  int div = 0;
  
  do {
    system("clear");
    printf("Digite um número inteiro e positivo: ");
    scanf("%d", &x);
  } while (x <= 0);
  
  for (i = 1; i <= x; i++) {
    if (x % i == 0) { 
     div++;
    }
  }
    
  if (div == 2)
    printf("O número %d é primo!", x);
  else
    printf("O número %d não é primo!", x);

  return 0;
}

Scripts recomendados

Análise combinatória

Binário para decimal

Transformação de Matriz em Matriz Transposta

Introdução a C

Maior de dois numeros

Comentários

[1] Comentário enviado por Gigatesla boy em 24/05/2010 - 19:21h

Belo algoritimo :)

Para implementá-lo ele poderia dividir apenas por numeros primos, ao inves de todos menos que ele. Afinal, todo numero que é composto é produto de um primo

4 0

[2] Comentário enviado por oberlan em 24/05/2010 - 19:48h

Uma forma de deixar o algorítmo mais eficiente é usar a seguinte função:

bool isPrimo(int n){

if(n<5 || n%2==0 || n%3==0)
return (n==2||n==3);

int maxP = sqrt(n)+2;
for(int p=5; p<maxP; p+=6)
if(n%p==0||n%(p+2)==0)
return false;

return true;
}

4 0