Finding the largest prime factor from a user input number

[Duthomhas]

I haven't actually been following this thread, but as a "relax" exercise, I tried to write myself an "is prime" function off the top of my head. My first thought was a sieve approach.

I first wrote a function that maintained a static internal std::set<>, but then I thought it might be nice to have access to that set outside of just checking to see if a number is prime.

So I rewrote it thus:

#include <ciso646>
#include <set>

#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH

template <typename T = unsigned long int>
struct primes: public std::set <T>
  {
  // The list of primes is partitioned into lower primes (which are all
  // sequential) and higher primes (which are not necessarily sequential, but
  // were found to be prime by previous invocations of this algorithm).
  //
  // When updating the list, we need to start with the next possible
  // sequential prime, so as not to miss anything. Since our list is actually
  // a set, adding a prime from the 'higher primes' partition has the effect
  // of simply transferring it to the 'lower primes' partition.
  //
  // We track the partitions by simply remembering the largest prime number
  // in the 'lower primes' partition.
  //
  T last_sequential;

  primes()
    {
    this->insert( 2 );
    this->insert( 3 );
    this->insert( 5 );
    last_sequential = 5;
    }

  bool isprime( const T& n )
    {
    if (n < 2) return false;
    if (this->count( n )) return true;

    // Does (any known prime p) divide n?
    foreach (const T& p, *this)
      {
      if ((n % p) == 0) return false;
      }

    // Did we check all possible primes <= sqrt( n )?
    // If not, we need to grow our 'lower primes' partition.
    T p = last_sequential;
    while ((n / p) > p)
      {
      p += 2;
      if (isprime( p ))
        {
        last_sequential = p;
        // Is the new found prime a divisor of n?
        if ((n % p) == 0) return false;
        }
      }

    // If we get this far, then n is prime.
    // Add it to our 'higher primes' partition.
    this->insert( n );
    return true;
    }
  };

There are a few other checks I could have put in there.. but it works pretty quickly for any n ten digits long or less. (It fails for larger numbers, but I'm not sure why... I haven't investigated yet.)


I was pretty pleased with myself until I realized there are are much quicker methods of finding primes than using E's sieve.

Here's a site all about more advanced methods.
http://primes.utm.edu/prove/

Now I feel stoopid.