[Ajuda] Optimizar Código

[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?

[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. 😉

[casdio]

Mas assim ele não vai continuar a calcular, mesmo depois de encontrar o maior factor?

[Ferreira]

Não. Porque havia de continuar?

[casdio]

Não. Porque havia de continuar?

Porque vou começar em 2 e acabar em n.

Acho que não estou a perceber  ?

[Ferreira]

A ideia é ir procurando os menores factores até que tenhas apenas um primo. E esse será o menor factor.