Project Euler #3: Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

 

The answer is 6857, as surmised by the following program.

#include <iostream>
#include <math.h>

int main(void)
{
	unsigned long long factoredNumber = 600851475143;
	unsigned long long seed = 2;
	// Could limit the search the search to less than square root of factoredNumber, due to it being composite
	while(pow(seed, 2) <= factoredNumber)
	{
		// While the "seed" is now a factor of factoredNumber
		while(factoredNumber%seed == 0)
		{
			// Divide and replace
			factoredNumber = factoredNumber / seed;
		}
		// Iterate
		seed += 1;
	}
	std::cout << factoredNumber;
        return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *