Numeros Primos

[Binder]

Olá pessoal, não estou encontrando um algoritimo para achar numeros primos em C.Pesquisei na net sobre vários(crivo de eratóstenes,etc) mas não entendi.

Queria fazer uma função que receba um numero qualquer, e retorna 1 se numero informado é primo, e 0 (zero) senão for primo.

alguém saberia me dizer um simples? Obrigado.

[mJi]

Um número é primo quando for divisível apenas por 1 e por ele mesmo.

Levando em conta que a partir da metade do número em questão já não é possível encontrar nenhum divisor, a melhor maneira é pegar tal número, fazer sucessivas operações de resto de divisão, de 2 até a metade do número. Caso haja algum resto de divisão igual a zero, o número não é primo, pois há outros divisores além dele mesmo e 1. Ao contrário, é primo.

[Binder]

Opa, obrigado pela atenção mJi, fiz um código abaixo, porém não sei se está certo. Pois o enunciado do exercício pede para retornar um valor, e eu não sei como mostrar em tela, se o numero é primo ou não.

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

  int primo(int num)
{
   int i, aux=1;
   for (i=2; i<num; i++) 
   {
        if (num % i == 0) 
        {
            return (0);
            break;
        }
        else
        {
            return (1); 
            break;
        }
   }
      
}
  
  int main () {
       
   int numero,resp;   
      
   printf("Digite um numero:");   
   scanf("%d",&numero);   
      
   resp = primo(numero);   
   
   printf("resultado\n",resp);
   system("pause");   
}//main

Editado Novembro 28, 2011 por Prog_Junior

[mJi]

Sobre a função:

int primo(int num){
    int i, aux=1;
   
    for (i=2; i<num; i++){
        if (num % i == 0){
            return (0);
            break;
        } else {
            return (1);
            break;
        }
   }
}

Há alguns erros de lógica. -Primeiramente, você pode fazer o loop enquanto 'i' for menor que a metade de 'num'. A partir da metade, já não será possível encontrar divisores. -Os 'breaks' não são necessários. -Quando o resto da divisão não for '0', você o loop pára (por causa do return). Ele deve continuar testando até chegar ao fim do loop ou até encontrar um divisor. Uma maneira de se fazer seria...

int primo(int num){
    int i;

    for (i=2;i<=num/2;i++){
        if (!(num%i))
            return (0);
    }
    return(1);
}

Ou seja... Recebe o número, e vai fazendo restos da divisão deste numero por 'i', que vai de 2 até a metade do número. Quando o resto da divisão for '0', retorna 0, pois o número não é primo. Se acabar o loop sem dar o return, ele dá return(1), pois o número é primo. Para mostrar o resultado, basta pegar o retorno e comparar: Se for 1 é primo, se for 0, não o é. Dá pra fazer assim:

if(primo(numero))
        printf("Este numero e primo.");
    else
        printf("Este numero não e primo.");

[Binder]

Olá mJi, muito obrigado pela explicação, porém eu estive testando e verifiquei que quando insiro os numeros: -1, 0, 1, ele diz que é numero primo, Por definição não são números primos.

Como poderia fazer esse controle? no main ou dentro da função? Obrigado.

[mJi]

Ah, se é pra pensar nas excessões, tem de fazer a verificação na função...

Antes de ir para o loop, coloque um if.

Se 'num' for negativo, for igual a zero, ou for igual a 1, retorne 0.

[Binder]

Muito obrigado mJi, fiz o que você falou e está funcionando. Abraço.

int primo(int num)
 {
    int i;
    if (num == -1 || num == 0 || num == 1)
    {
       return(0);         
    } 
    for (i=2;i<=num/2;i++)
    {
       if (!(num%i))
       return (0);
    }
    return(1);
}

Editado Novembro 28, 2011 por Prog_Junior