The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
    I know what you're thinking. Not hard at all... That's what I thought too but I had a bit of a problem. I had the code written up for the test input (13195) in about 20 minutes but when I substituted the actual number (600851475143) my compiler complained about it being too large! This caused some serious problems. I was lost for days trying to find out what to do. I used a thing called BigInteger library when I did this problem in C++ but that library isn't available for C. I was asking people on IRC channels and I got some good help of this one guy. He told me that my compiler (Code::Blocks) was a C89 compiler and a number that long needed a C99 compiler so it could store it in a long long int.
&ngsp   Talk about frustrating! I tried to install gcc but I couldn't get it to download! The icing on the cake was that if I had a 64-bit machine, I would have had it but seeing as I don't, I had to find an alternative. That alternative is This. An online C compiler that lets you download the .exe file! It suited my needs perfectly as it compiled it no bother and I got my code finished. I can't give an execution time for this problem but it was fast ;P So here's the code:
#include <stdio.h>
#include <math.h>
#define NUMBER 600851475143
int isPrime(int test)
{
int i=0;
int calculateTo=( (int) sqrt(test) );
for(i = 3; i <= calculateTo; i+=2)
{
if(test % i == 0)
{
return 0;
}
}
return 1;
}
int main()
{
int highest=0;
int i=0;
while(1)
{
for(i=3; ; i+=2)
{
if(isPrime(i))
{
if(NUMBER%i==0)
highest=i;
if(i>=(sqrt(NUMBER)))
goto END;
}
}
}
END:
printf("%d", highest);
return 0;
}
    I guess that's just about it!
       NotMyFault
Youre awsome
ReplyDelete