Ir ao conteúdo
  • Cadastre-se

C Programinha simples: como acelerar esse processamento?


kazamuru

Posts recomendados

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?

 

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

#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;

 

Link para o comentário
Compartilhar em outros sites

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.

  • Curtir 2
Link para o comentário
Compartilhar em outros sites

@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.

 

  • Curtir 1
Link para o comentário
Compartilhar em outros sites

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

}

 

  • Curtir 3
Link para o comentário
Compartilhar em outros sites

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.

 

 

 

 

 

 

  • Curtir 3
Link para o comentário
Compartilhar em outros sites

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!

  • Haha 1
Link para o comentário
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...