C Número Primo programa c

Diógenes Dantas Lélis Jr · 11 de setembro de 2019

Como eu faço para o programa mostrar todos os números primos de 2 a 999 usando while e if?

devair1010 · 12 de setembro de 2019

@Diógenes Dantas Lélis Jr o único número primo que é par é o 2 , então use o if para verificar se o número é par e se for então não é primo , e se não for verifique se o número é divisível por algum outro número de 2 até o número sem deixar resto , e para isso use um for , e o comando mod % ==0 , se for zero não tem resto e é primo , e vai assim até o valor máximo , faça seu código e poste aqui para vermos como está e em que podemos ajudar ,

Diógenes Dantas Lélis Jr · 12 de setembro de 2019

#include <stdio.h>

int main(){
  int n,i,dv,t;
  t = 1;
  for(n = 2 ; n<=999; n++){
    for(i = 1; i<n; i++){
      dv = n%i;
      t = t + 1;
    }
    if(t == 0){
      printf("erro");
    }
   if(t == 2){
     printf("%d ", n);
   }  
}
  
  return 0;
}

arfneto · 13 de setembro de 2019

15 horas atrás, Diógenes Dantas Lélis Jr disse:

#include <stdio.h>

int main(){
int n,i,dv,t;
t = 1;
for(n = 2 ; n<=999; n++){
for(i = 1; i<n; i++){
dv = n%i;
t = t + 1;
}
if(t == 0){
printf("erro");
}
if(t == 2){
printf("%d ", n);
}
}


return 0;

}

Olá!

Mas não era pra usar while() e if() ?

arfneto · 13 de setembro de 2019

Olá!

Este é um jeito clássico de escrever a função

int                retorna_um_se_primo(unsigned int n)
{
    if (n < 2)      return 0;
    if (n == 2)     return(1);
    if (n % 2 == 0) return(0);
    unsigned int maior = (unsigned int) sqrt( (double) n);
    unsigned int fator = 3;
    while (fator <= maior)
    {
        if (n % fator == 0) return 0;
        fator += 2;
    }    // end while
    return 1;
}    // end retorna_zero_se_primo()

Muitos dos exemplos online tem preguiça de calcular o maior fator, outros testam o loop para todos os pares inutilmente já que de início se sabe que 2 é o único primo par. Outros testam com o fator 2 talvez sem necessidade

Essa função aí então, como dá pra imaginar pelo nome, retorna um se o número é primo

Convém usar unsigned int porque dá pra usar até números maiores, até... UINT_MAX o maior valor que dá pra usar em uma variável dessas. Esse trecho

    i = retorna_um_se_primo(UINT_MAX);
    printf("\n\n retorna_um_se_primo(UINT_MAX=%u) retornou %u\n", UINT_MAX, i);

mostraria

 retorna_um_se_primo(UINT_MAX=4294967295) retornou 0

São dez dígitos. Essas constantes tipo UINT_MAX estão em geral em limits.h e convém incluir isso no programa por segurança

#include "limits.h"

adicionado 51 minutos depois

Não vi problema em postar um exemplo porque tem milhões desses online

Mas fiquei pensando: como conferir um trem desses?

Como em geral a gente aprende sobre números primos antes de aprender sobre programação e isso está no ensino fundamental, pensei no Crivo de Eratóstenes que a gente vê no ensino fundamental: Você pega uma folha de papel e escreve uma lista de números e separa o dois como primo. Aí marca os múltiplos de 2. Pega o próximo não marcado: 3. E marca os múltiplos, e continua até ficarem só os primos na tabela. Foi criado há mais de 2 mil anos.

Eis um desses para 100

Sobre o crivo de Eratóstenes na WikiPedia

Aí pensei que seria legal poder conferir a função

retorna_um_se_primo(unsigned int);

usando um crivo. Claro que marcar uns 10 números tudo bem, mas uns 900 já não dá né? Uma ocasião para escrever um crivo virtual grande. Em C, porque não. E aí pegar os primos e conferir na tabela gigante. E para não ficar na dúvida conferir a tabela gigante vendo se os números são mesmo primos chamando nossa função....

Pensei numa função assim:

unsigned int    proximo_primo(unsigned int);

que eu pudesse chamar e que a cada vez ela me retornasse o próximo primo. Para iniciar eu chamaria com o próprio número como argumento e a partir daí eu chamaria com argumento 0 e ela devolveria o próximo. Bem conveniente.

Se ela existisse, eu poderia escrever essa outra:

unsigned int    mostra_os_primos(unsigned int);

que faria exatamente o que o problema pedia: mostrar os primos de 2 até n inclusive. Podia ser assim escrita:

unsigned int    mostra_os_primos(unsigned int n)
{
    unsigned int l = limita_memoria(n);
    if (l < n)
    {    // nao deu: o valor foi limitado
        printf(    "Limite de memoria %dKB: o maior primo foi limitado de %u para %u",
            LIMITE_A_ALOCAR_KB, n, l        );
    }
    unsigned int r = proximo_primo(l);
    if (r < 0)
    {
        printf("Erro ao iniciar sequencia: %d\n", r);
        return(r);
    }
    printf("\n\nPrimos ate %u (inclusive)\n\n", n);
    unsigned int i = 0;
    while ((r = proximo_primo(0)) != 0)
    {
        printf("%10u ", r);
        i += 1;
        if (i % 10 == 0) printf("\n");
    } while (r > 0);
    return i;
}    // end mostra_os_primos()

Ficou até grande porque eu inseri uns testes. Mas é só isso: inicia a sequência chamando por exemplo

mostra_os_primos(900);

e aí a cada vez que chamar com

mostra_os_primos(0)

volta o próximo primo ou zero se acabaram. Se estiver tudo certo, esse trecho de programa

    i = mostra_os_primos(lim);
    printf("\n\nEncontrados %u primos\n", i);

mostraria

Primos ate 900 (inclusive)

         2          3          5          7         11         13         17         19         23         29
        31         37         41         43         47         53         59         61         67         71
        73         79         83         89         97        101        103        107        109        113
       127        131        137        139        149        151        157        163        167        173
       179        181        191        193        197        199        211        223        227        229
       233        239        241        251        257        263        269        271        277        281
       283        293        307        311        313        317        331        337        347        349
       353        359        367        373        379        383        389        397        401        409
       419        421        431        433        439        443        449        457        461        463
       467        479        487        491        499        503        509        521        523        541
       547        557        563        569        571        577        587        593        599        601
       607        613        617        619        631        641        643        647        653        659
       661        673        677        683        691        701        709        719        727        733
       739        743        751        757        761        769        773        787        797        809
       811        821        823        827        829        839        853        857        859        863
       877        881        883        887

Encontrados 154 primos

Como esperado. O argumento %u para printf() indica um valor inteiro sem sinal. São 10 valores por linha e tem tantos espaços entre os dígitos porque está preparado para listar primos de até 10 dígitos. Não muito útil aqui, admito.

Como conferir isso?

Agora ficou fácil: temos duas fontes de primos: usamos o crivo e pegamos um por vez ou pegamos os números e chamamos a função: então podemos jogar um contra o outro e não pode haver diferença, já que falamos de matemática inteira.

Confere os primos contra o crivo

int    compara_primos_com_crivo(unsigned int n)
{
    proximo_primo(n);    // prepara crivo
    for (unsigned int i = 2; i <= n; i++)
    {
        int r = retorna_um_se_primo(i);
        if (r == 1)
        {    // primo. então deve ser o proximo d lista
            int s = proximo_primo(0);
            if (i != s) return 0;
        }    // end if
    }    // end for
    return 1;    // tudo ok: valores indenticos
}    // end compara_primos_com_crivo()

Essa testa os números do crivo usando a função.

compara_primos_com_crivo(900)

por exemplo monta a tabela e depois no loop compara cada primo encontrado com o próximo do crivo. Claro, deve ser o mesmo número. Compara todos e retorna zero se deu m#$% ou 1 em caso de esperado sucesso.

Testa os números no crivo usando a função retorna_um_se_primo():

int                testa_crivo_contra_funcao(unsigned int n)
{
    unsigned int r = proximo_primo(n);    // prepara crivo
    
    if (r != 0) return 1;    // deu erro
    unsigned int i = 0;
    while ((r = proximo_primo(0)) != 0)
    {
        i = retorna_um_se_primo(r);
        if (i != 1)
        {
            return 0;    // deu pau: no crivo diz que e primo mas a funcao nao
        }    // end if
    }    // end while
    return 1;
}    //    end testa_crivo_contra_funcao()

O simples: pega cada primo que veio do crivo ao chamar proximo_primo(0) e testa com a função. Tem que ser todos bem iguais certo?

Então se eu rodar isso para lim=900

    i = mostra_os_primos(lim);
    printf("\n\nEncontrados %u primos\n", i);

    // agora testa a funcao e compara com os valores obtidos do crivo de eratostenes
    i = compara_primos_com_crivo(lim);
    if (i == 1)
        printf("Testando primos contra os marcados no crivo: sem surpresas. Todos os valores coincidem\n");
    else
        printf("Testando primos contra os marcados no crivo: Algo errado!\n");

    // agora testa o crivo e com a funcao verifica se todos sao primos
    i = testa_crivo_contra_funcao(lim);
    if (i == 1)    printf("Testando os valores do crivo com a funcao: sem surpresas. todos os valores confirmados\n");
    else
        printf("Testando os valores do crivo com a funcao: Algo errado\n");

    i = retorna_um_se_primo(UINT_MAX);
    printf("\n\n retorna_um_se_primo(UINT_MAX=%u) retornou %u\n", UINT_MAX, i);
    return 0;

devo ver

Primos ate 900 (inclusive)

         2          3          5          7         11         13         17         19         23         29
        31         37         41         43         47         53         59         61         67         71
        73         79         83         89         97        101        103        107        109        113
       127        131        137        139        149        151        157        163        167        173
       179        181        191        193        197        199        211        223        227        229
       233        239        241        251        257        263        269        271        277        281
       283        293        307        311        313        317        331        337        347        349
       353        359        367        373        379        383        389        397        401        409
       419        421        431        433        439        443        449        457        461        463
       467        479        487        491        499        503        509        521        523        541
       547        557        563        569        571        577        587        593        599        601
       607        613        617        619        631        641        643        647        653        659
       661        673        677        683        691        701        709        719        727        733
       739        743        751        757        761        769        773        787        797        809
       811        821        823        827        829        839        853        857        859        863
       877        881        883        887

Encontrados 154 primos
Testando primos contra os marcados no crivo: sem surpresas. Todos os valores coincidem
Testando os valores do crivo com a funcao: sem surpresas. todos os valores confirmados

E as duas linhas no final garantem que está tudo ok.

E a tal função que cria o Crivo de Eratóstenes? São duas coisas distintas: quando chama com o valor cria a tal estrutura, quando chama com zero vai devolvendo os caras, como faz rand(). Essa abaixo funciona

unsigned int    proximo_primo(unsigned int n)
{
    static unsigned int*    valores;
    static unsigned int     proximo, limite, indice, tamanho;
    unsigned int            j, k;
    ////////////////////////////////// prepara tudo e retorna
    unsigned int i = 0;
    static int     eraDois;

    if (n == 1) return (-1);
    if (n > 0)
    {    // chamada inicial: prepara tudo
        if (n == 2)
        {
            eraDois = 1;
            return 0;
        }
        else
        {
            eraDois = 0;
            if (valores != NULL) free(valores);                // se chamou de novo apaga tudo
            tamanho = ((n - 1) / 2);                        // so os impares
            i = tamanho * sizeof(unsigned int);
            valores = malloc(i);        // aloca o necessario
            if (valores == NULL) return -1;
            for (j = 0; j < tamanho; j++) valores[j] = 3 + j + j;
            limite = n;
            proximo = 2;
            indice = 0;
        }
        return 0;
    }    //    end if
    ////////////////////////////////// devolve o proximo primo
    if (eraDois == 1)
    {
        proximo = 0;
        eraDois = 0;
        return (2);
    }
    if (proximo == 0)     return( 0);
    if (valores == NULL) return(-2);
    if (proximo == 2)
    {
        proximo = 3;
        return 2;        // unico primo par
    }
    k = proximo;        // a partir de 3
    for (j = indice + k; j < tamanho; j += k)valores[j] = 0;    // marca os multiplos
    for (j = indice + 1; j<tamanho; j++)
    {
        if (valores[j] <= 0) continue;
        proximo = valores[j];
        indice = j;
        return k;
    }    // end for
    proximo = 0;
    return k;
}    // end proximo_primo()

Nada mágico. Note que não tem multiplicações ou módulo % ou funções exóticas. Apenas soma e tabula, exatamente como Eratóstenes fez entre 285 e 194 a.c. Mas usa memória e tem uma constante mágica que limita o tamanho do crivo virtual em K bytes

#define    LIMITE_A_ALOCAR_KB    (32768)

Mas dá pra ir bem longe. Até uns 10 dígitos. E depois é só um passatempo. O código de main() abaixo aceita o limite como argumento na linha de comando e assume 900 que é o valor pedido. Assim a gente pode testar com facilidade sem ter que compilar o programa de novo. E já usa a função para testar o crivo e vice e versa.

Se você usar

crivo
ou
crivo 900

vai gerar o que está acima

int main(int argc, char** argv)
{
    unsigned int n;
    if (argc > 1)    n = strtoul(argv[1], 0, 0);
    else
        n = 900;
    unsigned int    i = 0;
    unsigned int    lim = limita_memoria(n);

    printf("\n\nTestando com n=%u\n", lim);
    if (lim < n)
    {
        printf("Valor original %u truncado por falta de memoria para o crivo\n", n);
        printf("Memoria reservada = %uKB\n", LIMITE_A_ALOCAR_KB );
    }    // end if

    i = mostra_os_primos(lim);
    printf("\n\nEncontrados %u primos\n", i);
    // agora testa a funcao e compara com os valores obtidos do crivo de eratostenes
    i = compara_primos_com_crivo(lim);
    if (i == 1)
        printf("Testando primos contra os marcados no crivo: sem surpresas. Todos os valores coincidem\n");
    else
        printf("Testando primos contra os marcados no crivo: Algo errado!\n");
    // agora testa o crivo e com a funcao verifica se todos sao primos
    i = testa_crivo_contra_funcao(lim);
    if (i == 1)    printf("Testando os valores do crivo com a funcao: sem surpresas. todos os valores confirmados\n");
    else
        printf("Testando os valores do crivo com a funcao: Algo errado\n");

    i = retorna_um_se_primo(UINT_MAX);
    printf("\n\n retorna_um_se_primo(UINT_MAX=%u) retornou %u\n", UINT_MAX, i);
    return 0;

}    // end main()

E se fosse um milhão? eis o final para

crivo 1000000

Ainda bem que uma função conferiu a outra !!!

Eis o final para 1 milhão, já conferidos

    998857     998861     998897     998909     998917     998927     998941     998947     998951     998957
    998969     998983     998989     999007     999023     999029     999043     999049     999067     999083
    999091     999101     999133     999149     999169     999181     999199     999217     999221     999233
    999239     999269     999287     999307     999329     999331     999359     999371     999377     999389
    999431     999433     999437     999451     999491     999499     999521     999529     999541     999553
    999563     999599     999611     999613     999623     999631     999653     999667     999671     999683
    999721     999727     999749     999763     999769     999773     999809     999853     999863     999883
    999907     999917     999931     999953     999959     999961     999979     999983

Encontrados 78498 primos
Testando primos contra os marcados no crivo: sem surpresas. Todos os valores coincidem
Testando os valores do crivo com a funcao: sem surpresas. todos os valores confirmados

Para quem queria saber o maior primo menor que 1 milhão: 999983.