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.