### Finding the largest prime factor from a user input number

Pages: 12
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:

 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162`` ``````#include #include #include #define foreach BOOST_FOREACH template struct primes: public std::set { // 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.