Monday, June 14, 2010

Project Euler Problem 3 in C

    I hated this problem. It was so awkward. I'll explain after I post the description:


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

1 comment: