Will Clausen's Website

Categories
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.

Leave a Reply

Your email address will not be published.