WCW

# Solution: Project Euler Problem 3

The Problem:

What is the largest prime factor of the number 600851475143 ?

My solution (in C++):

```
// Author: Will Clausen
//
// Date: Jan 6, 2013
//
// This program will solve problem 3 of Project Euler

#include
#include
#include
#include

using namespace std;

// This function returns the largest prime factor of a
// number given as an argument
size_t largestPrime(size_t Num)
{
size_t remaining = Num;
set<size_t> primes;

// Handle the case where the number is even
if (remaining % 2 == 0) {
primes.insert(2);
}

while (remaining % 2 == 0) {
remaining /= 2;
}

// This is going to be an unorthodox for-loop
// where the rhs of the comparison step is
// modified within the loop.
for (size_t i = 3; i <= size_t(sqrt(remaining)); i += 2) {
if (remaining % i == 0) {
cout << "The prime is: " << i << endl;
remaining = remaining/i;
cout << "Now the number remaining is: " << remaining << endl; 			primes.insert(i); 			i = 3; 		} 	} 	// The number itself might be prime, so check that case. 	if (remaining > 3) {
primes.insert(remaining);
}

// Loop throught the set and find the largest prime.
size_t maxPrime = 1;
for (set<size_t>::iterator it = primes.begin(); it != primes.end(); ++it) {
if (*it > maxPrime) {
maxPrime = *it;
}
}

return maxPrime;
}

// Solution: 6857

```

This may be faster if I pre-generate primes less than the input using the Sieve of Eratosthenes method, then dividing by those primes.