Studiose Well I guess that's that.

Project Euler #3

Woo, that one was harder than I would have liked. Okay, well not so much hard, but tedious. My first couple iterations of this program took more than 20 minutes to find number I eventually found out I didn't need! But I eventually optimized it and found the answer, and wrote it in a way so that if I ever encounter this problem somewhere else with an even bigger number I'll be ready.

So First off, I had to write two of my own functions, with a bit of help from the internet of course. One was a function for square rooting 64bit numbers:

double Sqrt64( double number )
{
	double t1 = 0, t2 = 0, t3 = 0;
	while( ( t1 * t1 ) <= number ) t1 += 0.1;

	t2 = t1;

	for( double c = 0; c < 10; c++ )
	{
		t3 = number;
		t3 /= t2;
		t3 += t2;
		t3 /= 2;
		t2 = t3;
	}

	return t3;
}

And the other function which would check if a number was Prime or not:

// Int64 is defined in my header as: #define Int64 _int64
bool IsPrime( Int64 Number )
{
	bool IsPrime = true;

	for( int i = 2; i < Number + 1; i++ )
	{
		if( i != Number && Number != 1 )
		{
			if( Number % i == 0 ) IsPrime = false;
		}
	}
	return IsPrime;
}

After those I could finally get to the actual solution to Problem 3, which used this C++ code written by me ( hurr ):

int Problem3()
{
	Int64 Answer = 0, Total = 1, Value = 600851475143;

	for( Int64 i = 1; i < Sqrt64( Value ); i++ )
	{
		if( IsPrime( i ) )
		{
			if( Value % i == 0 && i != Value )
			{
				Total *= i;
				if( Total == Value )
				{
					Answer = i;
					i = Sqrt64( Value );
				}
			}
		}
	}
	return Answer;
}

Basically what I'm doing in all of that is Defining 3 variables as 64 Bit Integers: Answer, which as before is going to be our return value, and solution. Total, which is used as a container to add the product of all prime factors found during run-time. And Value, which is just so I don't have to keep typing 600851475143 into the program a bunch.

After defining the variables we run through a for loop with an initial value of 1 that after incrementing cannot exceed the square root of our given Value, which in this case is 600851475143. Inside this loop we check if the initialized variable: 'i', is Prime using our handy dandy IsPrime() function. Within that conditional we have another that checks to see if i is a factor of our Value and isn't actually our value. After checking that we need to multiply i to our Total and then check if our Total has met our Value, when that happens we have found all Prime Factors of our given Value. If we have met our Value we assign the last given prime factor to our Answer and then set 'i' to the square root of our Value just so we get out of the loop. And bam, you have your answer to problem 3.