C Faça um programa que calcule a soma dos números primos abaixo de dois milhões

Anatanael Barbosa · 3 de fevereiro de 2019

Faça um programa que calcule a soma de todos os números primos abaixo de dois milhões.

Código que eu fiz.

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

int main()
{
    int i, j, somaPrim = 2, quantDiv = 0;

    /*
        i -> Contador de 3 a 2000000 obs. (inicia no 3 pois o unico numero primo par é 2) e (conta de 2 em 2)
        j -> Contador de 1 ate o i (atual) para verificar quantos divisores tem o numero
        quantDiv -> Quantidade de divisores o numero autal tem
        somaPrim -> soma dos primos (inicia no 2 pois o 2 é o unico numero primo par

    */

    for (i = 3; i <= 2000000; i += 2) {
        quantDiv = 0;
        for (j = 1; j <= i; j++) {
            if (i % j == 0) {
                quantDiv++;
            }

            // Se quantidade de divisores for maior que 2 sair do loop
            if (quantDiv > 2) {
                break;
            }
        }

        if (quantDiv == 2) {
            somaPrim += i;
        }
    }

    printf("A soma dos numeros primos abaixo de 2 milhoes eh: %d\n\n", somaPrim);

    system("pause");
    return 0;
}

Mesmo iniciando a soma dos primos com o 2 (pois é o único numero par primo), e com um loop para testar apenas números impares o programa não termina. Minha duvida é se entrou em um loop infinito ou são muitos cálculos.

isrnick · 3 de fevereiro de 2019

Para ver se o número tem divisores só precisa dividir até a raiz quadrada do número, não precisa testar até o próprio número.

E números ímpares só são divisíveis por números ímpares (quando tem divisores).

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

int main()
{
    int i, j, somaPrim = 2, raizQuad, primo;

    /*
        i -> Contador de 3 a 2000000 obs. (inicia no 3 pois o unico numero primo par é 2) e (conta de 2 em 2)
        j -> Contador de 1 ate o i (atual) para verificar quantos divisores tem o numero
        somaPrim -> soma dos primos (inicia no 2 pois o 2 é o unico numero primo par
        raizQuad -> calcula a raiz quadrada de i
        primo -> indica se o número é primo (1 = verdadeiro, 0 = falso)
    */

    for (i = 3; i <= 2000000; i += 2) {
        primo = 1;
        raizQuad = (int)sqrt(i); //Só precisa checar até a raiz quadrada do número
        for (j = 3; j <= raizQuad; j += 2) { //Números ímpares só são divisíveis por ímpares
            if (i % j == 0) {
                primo = 0;
                break;
            }
        }

        if (primo) {
            somaPrim += i;
        }
    }

    printf("A soma dos numeros primos abaixo de 2 milhoes eh: %d\n\n", somaPrim);

    system("pause");
    return 0;
}

Anatanael Barbosa · 4 de fevereiro de 2019

Em 03/02/2019 às 00:29, isrnick disse:

Para ver se o número tem divisores só precisa dividir até a raiz quadrada do número, não precisa testar até o próprio número.

E números ímpares só são divisíveis por números ímpares (quando tem divisores).


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

int main()
{
    int i, j, somaPrim = 2, raizQuad, primo;

    /*
        i -> Contador de 3 a 2000000 obs. (inicia no 3 pois o unico numero primo par é 2) e (conta de 2 em 2)
        j -> Contador de 1 ate o i (atual) para verificar quantos divisores tem o numero
        somaPrim -> soma dos primos (inicia no 2 pois o 2 é o unico numero primo par
        raizQuad -> calcula a raiz quadrada de i
        primo -> indica se o número é primo (1 = verdadeiro, 0 = falso)
    */

    for (i = 3; i <= 2000000; i += 2) {
        primo = 1;
        raizQuad = (int)sqrt(i); //Só precisa checar até a raiz quadrada do número
        for (j = 3; j <= raizQuad; j += 2) { //Números ímpares só são divisíveis por ímpares
            if (i % j == 0) {
                primo = 0;
                break;
            }
        }

        if (primo) {
            somaPrim += i;
        }
    }

    printf("A soma dos numeros primos abaixo de 2 milhoes eh: %d\n\n", somaPrim);

    system("pause");
    return 0;
}

O número 175 tem divisores acima da raiz quadrada.

Raiz quadrada 175 -> 13.2

Divisores 175 -> 1, 5, 7, 25, 35, 175

isrnick · 5 de fevereiro de 2019

1 hora atrás, Anatanael Barbosa disse:

O número 175 tem divisores acima da raiz quadrada.

Raiz quadrada 175 -> 13.2

Divisores 175 -> 1, 5, 7, 25, 35, 175

Divisores sempre vem em pares, ou seja para cara divisor d de um dado número n existe outro divisor que pode ser encontrado dividindo n/d. (Com a exceção do caso em que divisor é a igual a √n pois nesse caso o outro divisor encontrado será o próprio divisor original, pois n / √n = √n.)

No seu exemplo:

1 é divisor de 175, e 175/1 = 175 também é divisor de 175.

5 é divisor de 175, e 175/5 = 35 também é divisor de 175.

7 é divisor de 175, e 175/7 = 25 também é divisor de 175.

Daí vemos que 175 tem 6 divisores, mas sabendo os 3 primeiros podemos encontrar os outros 3.

Se fizer o mesmo para outros números vai notar que isto funciona para qualquer número, só precisamos saber metade dos divisores para encontrar todos os divisores dele. Então só precisamos achar metade dos divisores, pois a outra metade já fica implícita.

E queremos saber em que ponto devemos parar de procurar divisores tal que garanta que já tenhamos encontrado a primeira metade dos divisores. Então observe abaixo que enquanto os números da primeira metade dos divisores estão em ordem crescente 1, 5 e 7, os seus respectivos divisores correspondentes, decorrentes divisão de 175 pelo divisor, estão em ordem decrescente 175, 35 e 25.

1 -> 175

5 -> 35

7 -> 25

E vamos continuar testando números acima de 7 e ver onde os dois se encontram:

8 -> 175/8 = 21.875

9 -> 175/9 = 19,444

10 -> 175/10 = 17,5

11 -> 175/11 = 15,9091

12 -> 175/12 = 14,583

13 -> 175/13 = 13,462

14 ->175/14 = 12,5

Note neste último que o número da direita finalmente ficou menor que o da esquerda, logo passamos da metade, logo seria suficiente procurar por divisores apenas até o número 13.

Se pensar um pouco fica claro que a metade exata sempre vai estar no ponto onde os 2 lados são exatamente iguais, e esse ponto é na raiz quadrado do número analisado:

√175 -> 175/√175 = √175

Logo, para encontrar divisores de um número só precisamos checar números que sejam menor ou igual que a raiz quadrada do número para encontrar a primeira metade dos divisores, e a segunda metade pode ser calculada a partir destes divisores já encontrados.

No caso deste programa não estamos tentando achar todos os divisores dos números, apenas se existe algum divisor além de 1 e o próprio número, então basta checar até encontrar um divisor, mas se chegar na raiz quadrada sem encontrar nenhum divisor o número é primo.

Anatanael Barbosa · 5 de fevereiro de 2019

20 horas atrás, isrnick disse:

Divisores sempre vem em pares, ou seja para cara divisor d de um dado número n existe outro divisor que pode ser encontrado dividindo n/d. (Com a exceção do caso em que divisor é a igual a √n pois nesse caso o outro divisor encontrado será o próprio divisor original, pois n / √n = √n.)

No seu exemplo:

1 é divisor de 175, e 175/1 = 175 também é divisor de 175.

5 é divisor de 175, e 175/5 = 35 também é divisor de 175.

7 é divisor de 175, e 175/7 = 25 também é divisor de 175.

Daí vemos que 175 tem 6 divisores, mas sabendo os 3 primeiros podemos encontrar os outros 3.

Se fizer o mesmo para outros números vai notar que isto funciona para qualquer número, só precisamos saber metade dos divisores para encontrar todos os divisores dele. Então só precisamos achar metade dos divisores, pois a outra metade já fica implícita.

E queremos saber em que ponto devemos parar de procurar divisores tal que garanta que já tenhamos encontrado a primeira metade dos divisores. Então observe abaixo que enquanto os números da primeira metade dos divisores estão em ordem crescente 1, 5 e 7, os seus respectivos divisores correspondentes, decorrentes divisão de 175 pelo divisor, estão em ordem decrescente 175, 35 e 25.

1 -> 175

5 -> 35

7 -> 25

E vamos continuar testando números acima de 7 e ver onde os dois se encontram:

8 -> 175/8 = 21.875

9 -> 175/9 = 19,444

10 -> 175/10 = 17,5

11 -> 175/11 = 15,9091

12 -> 175/12 = 14,583

13 -> 175/13 = 13,462

14 ->175/14 = 12,5

Note neste último que o número da direita finalmente ficou menor que o da esquerda, logo passamos da metade, logo seria suficiente procurar por divisores apenas até o número 13.

Se pensar um pouco fica claro que a metade exata sempre vai estar no ponto onde os 2 lados são exatamente iguais, e esse ponto é na raiz quadrado do número analisado:

√175 -> 175/√175 = √175

Logo, para encontrar divisores de um número só precisamos checar números que sejam menor ou igual que a raiz quadrada do número para encontrar a primeira metade dos divisores, e a segunda metade pode ser calculada a partir destes divisores já encontrados.

No caso deste programa não estamos tentando achar todos os divisores dos números, apenas se existe algum divisor além de 1 e o próprio número, então basta checar até encontrar um divisor, mas se chegar na raiz quadrada sem encontrar nenhum divisor o número é primo.

Muito obrigado pela excelente explicação. Fiz umas mudanças no código e funcionou perfeitamente.

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

int main()
{
    int i, j, quantDiv = 0;
    float somaPrim = 2;

    /*
        i -> Contador de 3 a 2000000 obs. (inicia no 3 pois o unico numero primo par é 2) e (conta de 2 em 2)
        j -> Contador de 1 ate o i (atual) para verificar quantos divisores tem o numero
        quantDiv -> Quantidade de divisores o numero autal tem
        somaPrim -> soma dos primos (inicia no 2 pois o 2 é o unico numero primo par

    */

    for (i = 3; i <= 2000000; i += 2) {
        quantDiv = 2;
        // quantDiv = 2; -> Divisores o numero 1 e o proprio numero
        for (j = 3; j <= (int)sqrt(i); j += 2) {
            if (i % j == 0) {
                quantDiv += 2;
                // Incrementa 2 pois o teste é ate a raiz quadrada
                break;
                // Se entrar no if significa que quantidade de divisores eh maior que 2 logo sai do loop for
            }
        }

        if (quantDiv == 2) {
            somaPrim += i;
        }
    }

    printf("A soma dos numeros primos abaixo de 2 milhoes eh: %.0f\n\n", somaPrim);

    system("pause");
    return 0;
}

01º Modificação: Iniciei a variável 'quantDiv' com 2, pois todo numero já e divisível por ele mesmo e por 1, se encontrar algum outro divisor já pode sair loop retirando um 'if' desnecessário.

02º Modificação: O teste do 'for' é ate a raiz quadrada conforme a sua explicação.

03º Modificação: Modifiquei a variável 'somaPrim' para 'float' pois o resultado é superior ao espaço de uma 'int'.

Muito obrigado pelo auxilio.

isrnick · 5 de fevereiro de 2019

1 hora atrás, Anatanael Barbosa disse:

03º Modificação: Modifiquei a variável 'somaPrim' para 'float' pois o resultado é superior ao espaço de uma 'int'.

Se quiser manter usando um tipo inteiro poderia usar o tipo long ao invés de int, ou até long long se long não for o suficiente, só precisa lembrar de usar o especificador de tipo correto na função printf (%ld para long ou %lld para long long).

https://en.cppreference.com/w/c/io/fprintf

Anatanael Barbosa · 6 de fevereiro de 2019

41 minutos atrás, isrnick disse:

Se quiser manter usando um tipo inteiro poderia usar o tipo long ao invés de int, ou até long long se long não for o suficiente, só precisa lembrar de usar o especificador de tipo correto na função printf (%ld para long ou %lld para long long).

https://en.cppreference.com/w/c/io/fprintf

O long int não foi suficiente, me parece que o long long funcionou.

Realizei um teste com long int, long long, float e double.

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

int main()
{
    int i, j, quantDiv = 0;
    float somaPrim = 2;
    long int somaPrimLI = 2;
    long long somaPrimLL = 2;
    float somaPrimF = 2;
    double somaPrimD = 2;

    /*
        i -> Contador de 3 a 2000000 obs. (inicia no 3 pois o unico numero primo par é 2) e (conta de 2 em 2)
        j -> Contador de 1 ate o i (atual) para verificar quantos divisores tem o numero
        quantDiv -> Quantidade de divisores o numero autal tem
        somaPrim -> soma dos primos (inicia no 2 pois o 2 é o unico numero primo par

    */

    for (i = 3; i < 2000000; i += 2) {
        quantDiv = 2;
        // quantDiv = 2; -> Divisores o numero 1 e o proprio numero
        for (j = 3; j <= (int)sqrt(i); j += 2) {
            if (i % j == 0) {
                quantDiv += 2;
                // Incrementa 2 pois o teste é ate a raiz quadrada
                break;
                // Se entrar no if significa que quantidade de divisores eh maior que 2 logo sai do loop for
            }
        }

        if (quantDiv == 2) {
            somaPrim += i;
            somaPrimLI += i;
            somaPrimLL += i;
            somaPrimF += i;
            somaPrimD += i;
        }
    }

    //printf("A soma dos numeros primos abaixo de 2 milhoes eh: %f\n\n", somaPrim);

    printf("long int:  %ld\n\n", somaPrimLI);
    printf("long long: %lld\n\n", somaPrimLL);
    printf("float:     %f\n\n", somaPrimF);
    printf("double:    %lf\n\n", somaPrimD);

    system("pause");
    return 0;
}

O resultado do long long deu igual ao do double, porém o double que tem precisão maior que o float encontrou um resultado menor.

long int -> 11 79 908 154

long long -> 142 913 828 922

float -> 142 915 960 832

double -> 142 913 828 922

Sérgio Lembo · 10 de fevereiro de 2019

Gostei dessa discussão. Parabéns ao @isrnick pela solução da raiz quadrada que reduz de forma significativa a pesquisa. No número 10000 a pesquisa se encerra no 100. O código ficou bom mas ainda cabe um aprimoramento. A cada ciclo de loop do segundo for o processador tem que recalcular a raiz quadrada cujo valor será sempre o mesmo até que se alcance o valor da raiz quadrada. Eliminar o recálculo tornará o código mais eficiente (rápido).

A sugestão: criar mais uma variável, vou batizar de quadrado.

O código que está dessa forma:

for (i = 3; i < 2000000; i += 2) {

quantDiv = 2;

for (j = 3; j <= (int)sqrt(i); j += 2) {

ganharia essa forma:

for (i = 3; i < 2000000; i += 2) {

quantDiv = 2;

quadrado = (int)sqrt(i);

for (j = 3; j <= quadrado; j += 2) {

adicionado 7 minutos depois

OBS: Não se esqueça de declarar a variável.

isrnick · 10 de fevereiro de 2019

@Sérgio Lembo Meu programa original já tem a variável raizQuad para armazenar a raiz e não recalcular toda vez que rodar o loop.

A única correção necessária no meu programa é fazer somaPrim ser tipo long long.

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

int main()
{
    int i, j, raizQuad, primo;
    long long somaPrim = 2;

    /*
        i -> Contador de 3 a 2000000 obs. (inicia no 3 pois o unico numero primo par eh 2) e (conta de 2 em 2)
        j -> Contador de 1 ate o i (atual) para verificar quantos divisores tem o numero
        raizQuad -> calcula a raiz quadrada de i
        primo -> indica se o numero eh primo (1 = verdadeiro, 0 = falso)
        somaPrim -> soma dos primos (inicia no 2 pois o 2 eh o unico numero primo par
    */

    for (i = 3; i <= 2000000; i += 2) {
        primo = 1;
        raizQuad = (int)sqrt(i); //So precisa checar ate a raiz quadrada do numero
        for (j = 3; j <= raizQuad; j += 2) { //Numeros impares so sao divisiveis por impares
            if (i % j == 0) {
                primo = 0;
                break;
            }
        }

        if (primo) {
            somaPrim += i;
        }
    }

    printf("A soma dos numeros primos abaixo de 2 milhoes eh: %lld\n\n", somaPrim);

    system("pause");
    return 0;
}

Sérgio Lembo · 10 de fevereiro de 2019

@isrnick , desculpe não ter percebido. É que no último post do autor ainda não havia sido implantado o recurso e fui induzido ao erro.

Anatanael Barbosa · 11 de fevereiro de 2019

Obrigado pelas observações. Fiz as atualizações.

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

int main()
{
    int i, j, primo = 0, raizQuad;
    float somaPrim = 2;
    long int somaPrimLI = 2;
    long long somaPrimLL = 2;
    float somaPrimF = 2;
    double somaPrimD = 2;

    /*
        i -> Contador de 3 a 2000000 obs. (inicia no 3 pois o unico numero primo par é 2) e (conta de 2 em 2)
        j -> Contador de 1 ate o i (atual) para verificar quantos divisores tem o numero
        primo -> Se o resultado final for 1 então é primo senão não é primo
        raizQuad -> Calcula a raiz quadrada do i atual
        somaPrim -> soma dos primos (inicia no 2 pois o 2 é o unico numero primo par

    */

    for (i = 3; i < 2000000; i += 2) {
        primo = 1;
        raizQuad = (int)sqrt(i);
        for (j = 3; j <= raizQuad; j += 2) {
            if (i % j == 0) {
                primo = 0;
                break;
                // Se entrar no if significa que quantidade de divisores eh maior que 2 logo sai do loop for
            }
        }

        if (primo) {
            somaPrim += i;
            somaPrimLI += i;
            somaPrimLL += i;
            somaPrimF += i;
            somaPrimD += i;
        }
    }

    //printf("A soma dos numeros primos abaixo de 2 milhoes eh: %lld\n\n", somaPrim);

    printf("long int:  %ld\n\n", somaPrimLI);
    printf("long long: %lld\n\n", somaPrimLL);
    printf("float:     %f\n\n", somaPrimF);
    printf("double:    %lf\n\n", somaPrimD);


    system("pause");
    return 0;
}

Realizei um teste com long int, long long, float e double.

long int -> 11 79 908 154

long long -> 142 913 828 922

float -> 142 915 960 832

double -> 142 913 828 922

O resultado do long long deu igual ao do double, porém o double que tem precisão maior que o float encontrou um resultado menor. Porque ocorre isso ?

isrnick · 11 de fevereiro de 2019

14 minutos atrás, Anatanael Barbosa disse:

O resultado do long long deu igual ao do double, porém o double que tem precisão maior que o float encontrou um resultado menor. Porque ocorre isso ?

Exatamente por isso, o double é mais preciso e consegue armazenar a resposta correta deste problema sem erros, mas o float não é tão preciso e se torna necessário fazer arredondamentos nas casas menos significativas do número quando o número fica muito grande, nesse caso o erro no resultado final é positivo e o número ficou maior.

Sérgio Lembo · 12 de fevereiro de 2019

@Anatanael Barbosa e @isrnick . Estou em dúvidas se bebi demais ou se estou interpretando de forma errada por beber de menos. Como é que num range de 2 milhões de amostras foram encontradas quase 143 bilhões de ocorrências?

adicionado 12 minutos depois

Mais uma dúvida: se primo está declarado como int e até ganha um valor numérico e não como false / true, como é que na última condicional o teste é feito sem a comparação numérica? Enquanto não postam resposta vou consultar de novo Mr Scoth.

isrnick · 12 de fevereiro de 2019

4 horas atrás, Sérgio Lembo disse:

Estou em dúvidas se bebi demais ou se estou interpretando de forma errada por beber de menos. Como é que num range de 2 milhões de amostras foram encontradas quase 143 bilhões de ocorrências?

O programa não conta quantos primos tem, mas sim faz a soma de todos os números primos abaixo de 2 milhões.

4 horas atrás, Sérgio Lembo disse:

Mais uma dúvida: se primo está declarado como int e até ganha um valor numérico e não como false / true, como é que na última condicional o teste é feito sem a comparação numérica? Enquanto não postam resposta vou consultar de novo Mr Scoth.

Em C o valor 0 (zero) é igual a falso, e qualquer valor diferente de 0 (zero) é igual a verdadeiro. (Isso é válido em muitas linguagens de programação.)

(Na prática a biblioteca stdbool.h apenas define macros em que false expande para 0, e true expande para 1. https://en.cppreference.com/w/c/types/boolean )

E quem é Mr Scoth?

Sérgio Lembo · 12 de fevereiro de 2019

8 horas atrás, isrnick disse:

E quem é Mr Scoth?

Whisk escocês, são os melhores.

isrnick · 14 de fevereiro de 2019

Segue outra solução que fiz, ainda mais eficiente, usando o crivo de Eratóstenes:

https://pt.wikipedia.org/wiki/Crivo_de_Eratóstenes

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int main()
{
    bool primo[2000001] = {false};
    int i, j, n, raizQuad;
    long long somaPrim;
    
    n = 2000000;
    
    for (i = 2; i <= n; i++){
        primo[i] = true;
    }
    
    raizQuad = (int) sqrt(n);
    for (i = 2; i <= raizQuad; i++){
        if(primo[i]){
            for (j = i*i; j <= n; j += i){
                primo[j] = false;
            }
        }
    }
    
    somaPrim = 0;
    for (i = 2; i <= n; i++){
        if (primo[i]){
            somaPrim += i;
        }
    }
    
    printf("%lld\n", somaPrim);
    
    return 0;
}

O tempo de execução desse programa foi de 0.01s, o programa anterior que postei demora de 0.21s a 0.35s, mais de 20 vezes mais lento.

Sérgio Lembo · 14 de fevereiro de 2019

@isrnick , na instrução for i não tem que iniciar em 3 e ser acrescido de 2 a cada loop?

isrnick · 14 de fevereiro de 2019

44 minutos atrás, Sérgio Lembo disse:

@isrnick , na instrução for i não tem que iniciar em 3 e ser acrescido de 2 a cada loop?

Não, a ideia é diferente, não fica fazendo divisões pra ver se os números são primos.

No crivo de Eratóstenes inicialmente assume-se que todos os números no intervalo são primos (um vetor indica todos inicialmente como true), aí começando do primeiro primo conhecido, o 2, acha todos os múltiplos dele e elimina marcando como não-primos (muda a posição no vetor para false), aí segue até o próximo número após 2 que ainda consta como primo, que é 3, e marca todos os todos os múltiplos de 3 como não-primos, e segue para o próximo número que ainda consta como primo, que é 5, e assim por diante, continuando até chegar na raiz quadrada de 2 milhões que é o intervalo de números que desejamos identificar como primos ou não no nosso caso.

Ele usa a característica de que um número só pode ser múltiplo de números primos que vieram antes dele, então conforme vai eliminando os múltiplos dos primos já encontrados, todos os números não-primos no intervalo até o próximo número primo já terão sido eliminados e identificados como tal, sobrando só o próprio próximo número primo corretamente identificado na seqüência.

Dê uma lida no artigo da Wikipedia que dá mais detalhes de como o crivo de Eratóstenes funciona.

adicionado 32 minutos depois

Mas posso fazer uma modificação no algoritmo para eliminar os múltiplos de 2 primeiro separadamente, aí o incremento para encontrar os múltiplos dos outros números primos pode ser 2x o primo:

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int main()
{
    bool primo[2000001] = {false};
    int i, j, n, raizQuad;
    long long somaPrim;
    
    n = 2000000;
    
    for (i = 2; i <= n; i++){
        primo[i] = true;
    }
    
    for (j = 2*2; j <= n; j += 2){
        primo[j] = false;
    }
    
    raizQuad = (int) sqrt(n);
    for (i = 3; i <= raizQuad; i++){
        if(primo[i]){
            for (j = i*i; j <= n; j += 2*i){
                primo[j] = false;
            }
        }
    }
    
    somaPrim = 0;
    for (i = 2; i <= n; i++){
        if (primo[i]){
            somaPrim += i;
        }
    }
    
    printf("%lld\n", somaPrim);
    
    return 0;
}