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
/* 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á: