C Programinha simples: como acelerar esse processamento?

[kazamuru]

O exercício pede : "Faça um programa que calcule a soma de todos os números primos abaixo de dois milhões."

 

Eu fiz. Mas da forma que fiz está levando provavelmente bem mais de 1h para chegar ao resultado:

 

c.txt

 

Certamente existe um jeito muito melhor de fazer isso. Alguém pode me ajudar?

 

[Leonardo0308]

Boa tarde @kazamuru

 

Poderia postar o código aqui no fórum?

[kazamuru]

#include<stdio.h>


//verifica se o numero eh primo.
int primo(int n){

    int div=0, i;

    for(i=1;i<=2000000;i++){        //divide cada um dos numeros passados por 1 ate 2.000.000
        if(n%i==0)
            div++;            //a cada divisao exata incremento 'div'
    }

    if(div==2){                //se houver apenas 2 divisores, entao é primo e retorno 1 arbitrariamente.
        return 1;        
    }
    else
        return 0;

}

int main(){

    int i;
    int soma=0;
    int retorno;

    for(i=1;i<=2000000;i++){    //passa os numeros de 1 a 2.000.000 para a função 'primo'
        retorno = primo(i);

        if(retorno==1){        //se for primo (retorno =1) é somado à variavel 'soma'        
            soma+=i;
        }
    }

    printf("\nSoma: %d",soma);


    return 0;

 

[Leonardo0308]

Você não precisa dividir por 100000 números o numero 4 por exemplo.

 

Você só precisa dividir pelo numero-1 até o 2. por exemplo o 5 você só precisa dividir pelo 4,  3 e 2.

 

E a partir do momento que você saiba que ele foi dividido por um desses números você já pode sair do loop e ir para o próximo numero.

[kazamuru]

@Leonardo0308 É verdade! Eu modifiquei a função que verifica se é primo:

 

int primo(int n){

	int div=0, i;

	for(i=1;i<=n;i++){		//divide cada um dos numeros passados por 1 ate 2.000.000
		
		if(div==2)
			break;

		if(n%i==0)
			div++;			//a cada divisao exata incremento 'div'
	}

	if(div==2){				//se houver apenas 2 divisores, entao é primo e retorno 1 arbitrariamente.
		return 1;		
	}
	else
		return 0;

}

Fiz o calculo com 10.000 numeros e está muito mais rápido, obrigado. Será que ainda dá para melhorar isso? O calculo com 2kk ainda está muito demorado pelo que vi.

 

[Flávio Pedroza]

Tenta algo assim (não testado):

int primo(int n){

    int div=0, i;

    for(i=2;i<=n/2;i++){        //divide cada um dos numeros passados por 2 ate n/2
        if(n%i==0) return 0; //se achar pelo menos um divsor, já é considerado não primo
    }
    return 1; //completou o laço e não achou nenhum divsor? é primo com certeza

}

 

[Leonardo0308]

Sim, ainda tem 

 

Como eu havia dito, para o numero 10 por exemplo.

 

Eu sei que ele é divisível por 10 e 1, então por que irei calcula-los? entende?

 

E a partir do momento que eu sei que ele é divisível por 5, por que iria continuar o loop?

 

Tem uma função chamada break; que sai do loop.

 

se o seu div for igual a 1 você pode já retorna o "falso".

 

e se for igual a 0, parabéns você tem um numero primo.

 

 

 

 

 

 

[Gabriel_Moro]

dica: todo numero primo depois do 2 não é par

[Leonardo0308]

Como o @Flávio Pedroza  e o @Gabriel_Moro falaram, você pode descartar todos os números pares do loop, tirando o 2.

[kazamuru]

@Flávio Pedroza Tentei. Está calculado bastante rápido e pelo que testei esta correto. Mas o calculo dos primos ate 1kk deu um numero negativo (levou uns 3 minutos)  "-1104303640"

adicionado 2 minutos depois

@Leonardo0308 Vou tentar! De qualquer forma já melhorou muito!

[Leonardo0308]

@kazamuru , quando você finalizar as alterações, posta aqui para gente ver como ficou

[Flávio Pedroza]

Deve estar estourando o range da variável.

Muda o tipo da variável soma para unsigned long:

 

unsigned long soma=0;

 

E quando for imprimir na tela;:

    printf("\nSoma: %u",soma);

 

[kazamuru]

Esse foi o código que resolveu mais rápido. São 4 minutos e 30 segundos no meu i5 3.3ghz:

 

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

#include<stdio.h>

int primo(int n){

    int i;
    for(i=2;i<=n/2;i++){        
        if(n%i==0) return 0; 	
    }
    return 1; 			
}

int main(){

	int i;
	unsigned long soma=0;
	int retorno;

	for(i=2;i<=2000000;i++){							
		retorno = primo(i);

		if(retorno==1){				
			soma+=i;
		}
	}

	printf("\nSoma: %lu",soma);


	return 0;

Obrigado a todos pela ajuda!