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):

  1. divide the number by successive integers (each denoted by i) upto sqrt(n),
  2. 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<stdio.h>
#include<stdlib.h>
#include<math.h>

// 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<sqrt(aim); 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.

Advertisements

About liyao13

Yao Li is a web and iOS developer, blogger and he has a passion for technology and business. In his blogs, he shares code snippets, tutorials, resources and notes to help people develop their skills. Donate $5 to him for a coffee with PayPal at About Me page and read more professional and interesting technical blog articles. Follow him @Yaoli0615 at Twitter to get latest tech updates.
This entry was posted in ProjectEuler and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s