Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #57 da revista programar. Faz já o download aqui!

casdio

[Ajuda] Optimizar Código

Mensagens Recomendadas

casdio    0
casdio

Boas.

O objectivo do código é este (problema 3 do ProjectEuler para quem conhecer):

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Eu fiz este programa:

#include <stdio.h>

int primo(int n)
{
int i,j=1;

for(i=2;i<n/2;i++)
{
	if(n%i==0)
	{
		j=0;
		break;
	}
	else
		continue;
}
return j;
}

int main()
{
long int n,i;

printf("Nº: ");
scanf("%ld",&n);

for(i=n/2;i>0;i--)
{
	if(primo(i))
	{
		if(n%i==0)
		{
			printf("%ld\n",i);
			break;
		}
		else
			continue;
	}
	else
		continue;
}					
return 0;
}		

O problema é que isto já esteve mais de 2horas a correr e nada.

Aliás, estou a testar agora com o número 15 134 665 (o resultado é 37) e, ao fim de 13 min, ainda não acabou de correr.

Alguém me ajuda a optimizar o código sff?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Ferreira    0
Ferreira

Há alguns meses também andei a brincar com o Project Euler e tenho uma solução mais eficiente.

Fazes um ciclo de 2 até n. Sempre que encontras um factor de n, divides n por esse factor e continuas. Com isto ficas com um ciclo apenas até ao maior factor. ;)

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita a nossa Política de Privacidade