Números primos. Um inteiro é considerado primo se for divisível apenas por 1 e por ele mesmo. Por exemplo, 2, 3, 5 e 7 são primos, mas 4, 6, 8 e 9 não são.

(a) Escreva uma função que determine se um número é primo.

(b) Use essa função em um programa que determine e imprima todos os números primos entre 1 e 10000. Quantos desses 10000 números você realmente precisa testar antes de ter certeza de que encontrou todos os primos?

(c) Inicialmente, você poderia pensar que n/2 é o limite superior dentro do qual deveria testar para ver se um número é primo, mas você só precisa ir até a raiz quadrada de n. Por quê? Reescreva o programa e execute-o das duas maneiras. Estime a melhoria do desempenho

Passo 1

Fala Galera!!!Bora para mais um exercício!!!

Vamos definir uma função que verifique se um número é primo. Podemos fazer essa verificação criando uma função que analisa se um número divido por 2 possui resto ou não. Ou seja, n / 2. Onde n pode ser qualquer número inteiro. Caso o resto seja diferente de zero o número é primo. Portanto, a função criada será:

/* Definição da função primos */

int prime (int n){

/* contador*/

int loop2;

/* Fatores para encontrar os números primos */

for (loop2 =2; loop2

/* fator ecnontrado, não primo */

if (n % loop2 == 0){

return 0;

} /* fim do if */

} /* fim do for */

return 1; /* retorna 1 se for primo */

} /* fim da função primo */

Passo 2

Na letra (b) usaremos a função criada na letra (a) para verificar se um numero é primo. A ideia é colocar a função dentro de um laço de repetição que verifica todos os números de 1 até 10000. O programa criado será:

#include

/* Protótipo da função primos*/

int prime( int n );

int main(){

/* contador */

int loop;

/* contador do total de números primos encontrados */

int count = 0;

printf("Os número primos de 1 a 10000 são: \n");

/* loop de 1 até 10000 */

for(loop =1; loop

/* if se o número atual é primo */

if (prime (loop)){ /* chamada da função */

++count;

printf("%6d", loop);

/* nova linhas após os 10 primeiros números primos */

if (count % 10 == 0){

printf("\n");

} /* final if */

} /* final if */

} /* final for */

return 0;

Passo 3

Na letra (c) a função para definir se um número é primo é modificada para analisar a raiz quadrada de n. Agora iremos utilizar a função sqrt para fazer essa verificação. A função sqrt é uma função padrão da linguagem C. Para utilizar ela, precisamos da biblioteca . A função modificada será:

/* Definição da função primos */

int prime (int n){

/* contador*/

int i;

/* Fatores para encontrar os numeros primos */

for (i =2; i

/* fator ecnontrado, não primo */

if (n % i == 0){

return 0;

} /* fim do if */

} /* fim do for */

return 1; /* retorna 1 se for primo */

} /* fim da função primo */

Tudo pronto, agora só juntar tudo e ter o programa final.

Resposta

Portanto a resposta final para o nosso programa para letra (a) e (b) será:

Para a letra (c) o programa final será: