Project Euler 3

First time I thought about generating successive prime numbers to divide the aim number, whose reminder is zero. If the reminder is not zero, then the previous prime number is the largest prime factor of the aim number. But it doesn’t work, Floating Point Exception always displays. Code is following:

long int primegen(long int i)
{
long int temp_num;
temp_num = i;
if( temp_num % 2 == 0)
temp_num = 0;
else
{
int j;
long long int sqrt_result = (long long int)sqrt(temp_num);
for( j = 3; j < sqrt_result; j += 2)
{
if( ( temp_num % j ) == 0 ) temp_num = 0;
}
}
return temp_num;
}

int main()
{
long long int prime, prime_factor;
long long int aim;
aim = 600851475143;
int flag = 0;
long int count = 3;

while( flag == 0 )
{
if ( primegen( count ) > 0 );
{
prime = primegen( count );
if( ( aim % prime == 0 ) && ( prime <= aim ) )
prime_factor = prime;
else if ( prime > aim )
{
flag = 1;
}
}
count+=2;
}

printf(“The largest prime factor of the number 600851475143 is %lld\n”, prime_factor);

return 0;
}

After considering for some time, I cannot help checking solutions with Google. Then I found one solution in http://thetaoishere.blogspot.com/2008/05/largest-prime-factor-of-number.html

FindLargestPrimeFactor(n):

divide the number by successive integers (each denoted by i) upto sqrt(n),
when the remainder is 0, return the maximum among i and FindLargestPrimeFactor(n/i).
But in my eyes, it should be added the termination condition into the function FindLargestPrimeFactor(n):

If the reminder is 0, then return MAX( i , FindLargestPrimeFactor(n/i) ), but if the reminder is not zero until finish the whole loop and obviously, n is a prime number, so the recursion ends when it just returns n. My complete code is like this:

#include
#include
#include

// Find Largest Prime Factor
long long int FLPF(long long int i)
{
long long int aim;
long long int solution;
aim = i;
int counter_sol;

for( counter_sol=3; counter_sol{
if( aim % counter_sol == 0)
{

//printf(“The counter_sol is %d\n”, counter_sol);
solution = aim/counter_sol;
//printf(“The solution is %lld\n”, solution);
if( counter_sol < solution )
return FLPF(solution);
else return counter_sol;
}
}

return aim;
}

int main()
{
long long int aim;
long long int solution;
aim = 600851475143;
solution = 0;

printf(“The aim is %lld\n”, aim);
solution = FLPF(aim);
printf(“The solution is %lld\n”, solution);
return 0;
}

I feel I’m cheating because I borrowed the main idea from the website even though I add termination condition by myself.

I was trapped in the math procedure and the more efficient way is to find the smallest factor first and then find the solution which combine the main two steps into one, wonderful!

Two things learned from problem 3 in Project Euler:

1.C is not very suitable to figure out this kind of math problem. Some other language might be better like Python and Perl. Python is the unique required language in Pattern Recognition so that I will finish learning the syntax within 2 or 3 hours tonight.

2.Sometimes I cannot figure out the problem in Project Euler due to insufficient math knowledge. I will fix it from now on. Now I’m Baby Step now, I will figure out more problems since I enjoy this process.