I have some code done and I think it will eventually compute a valid answer for me. However, the spirit of these Project Euler problems is that they are computable by a reasonably powered computer in a minute or less. I've given the algorithm that I have 5 solid minutes to compute this, and it isn't finished. For the C++ inclined, here is my complete code:
[Reveal] Spoiler: Code
- Code: Select all
#include <iostream>
#include <cmath>
#include <set>
#include <cassert>
#include <fstream>
using namespace std;
template <typename T>
void intFiller(set<T>& p, unsigned long long largest);
template <typename T>
void primeFinder(set<T>& p, unsigned long long largest);
template <typename T>
void primeFactor(set<T>& p, unsigned long long biggest);
template <typename T>
ostream& operator<<(ostream& o, set<T> p);
int main()
{
unsigned long long n;
ofstream projTxt;
set<unsigned long long> primes;
projTxt.open("project3.txt");
cout << "Please specify largest possible prime: ";
projTxt << "Please specify largest possible prime: ";
cin >> n;
projTxt << n << endl;
intFiller(primes, n);
//Now primes is the set of positive integers on the interval [2,n]
primeFinder(primes, n);
//Now primes is the set of all prime numbers in the interval [2,n)
cout << primes;
cout << endl;
cout << "and the prime factors of " << n << " are: \n";
primeFactor(primes, n);
cout << primes;
if(projTxt.is_open())
projTxt << primes;
projTxt.close();
}
template <typename T>
void primeFactor(set<T>& p, unsigned long long biggest)
{
set<T>::iterator iterP = p.begin();
unsigned long long factor;
while(iterP!=p.end())
{
factor = *iterP;
if((biggest%factor)!=0)
{
p.erase(factor);
iterP = p.begin();
}
else
++iterP;
};
}
template <typename T>
void intFiller(set<T>& p, unsigned long long largest)
{
unsigned long long i;
for(i=2; i<=largest; ++i)
{
p.insert(i);
};
}
template <typename T>
void primeFinder(set<T>& p, unsigned long long largest)
{
set<T>::iterator iterP = p.begin();
unsigned long long i, k;
while(iterP!=p.end())
{
for(i=2; i<=sqrt(double(largest)); ++i)
{
for(k=2; (i*k)<=largest; ++k)
{
iterP = p.find(i*k);
if(iterP!=p.end())
p.erase(iterP);
};
};
};
}
template<typename T>
ostream& operator<<(ostream& out, set<T> p)
{
set<T>::iterator output;
if(!p.empty())
{
for(output=p.begin(); output!=p.end(); ++output)
{
out << *output;
out << endl;
};
};
return out;
}
Basically this code does the following:
1. Uses the Sieve of Eratosthenes to compute primes less than or equal to a given number.
2. Checks to see which of those primes does not evenly divide the given number, and strikes them out.
My code works over a fair range of numbers, but something like 600851475143 will just take ages. I feel like I need to seek mathematical advice on this and learn up a little more on prime numbers. I notice that the sieve of eratosthenes just keeps going until you get to multiples of numbers greater than the given number's square root. Is there some particular reason for this? Is there some way I can exploit this to take any sort of significant shortcut to finding the largest prime factor of a number?
