Question

Um número n é primo caso ele não seja divisível por nenhum outro número que
esteja no intervalo [2..n-1]. Ou seja, 5 é um número primo porque ele não é
divisível pelos valores 4, 3 e 2. Por outro lado, 8 não é primo pois ele é divisível
por 4 e 2. Crie uma função em C que receba um número n como entrada e
retorne 1 caso n seja um número primo e 0 caso contrário

0ba246d1f81ac9b6165b9928a9eb8c7e.pdf

Answer 1

int ehprimo( int numero ) { 
     if (numero %2 ==0 ) { 
           /* é par, não pode ser primo */ 
          return 0
     }
     int retorno = 1;
     for (int i=3 ; i< (numero/3)+1 ; i+=2 ) {
          if (numero % i == 0 ) { 
               return 0
          }
      }
      return 1
} 

Como funciona.
primeiro testamos se o número é divisível por 2, ou seja, resto da divisào por 2 for igual a 0. Dessa forma, agilizamos os testes. Exceto pelo 2, todos os números primos são ímpares.
O for começa com 3 e vai de 2 em 2 buscando uma divisão que dê resto 0.
Se achar alguma divisào que dê resto 0, o número não é primo. Retornamos 0.
Se chegar ao fim do for, significa que não achou divisor algum, retorna 1. O for só precisa ir até mais ou menos um terço do valor do número. Pois se ele já passou pela divisào por 3 ... o maior divisor dele deve ser menor que um terço.