The basic idea is pretty simple. We have an accumulator that stores the product of all primes up to N; if the GCD of the accumulator and the current index isn't one, then (the index is prime and) the accumulator is multiplied with the index. The algorithm is quite fast due to the rate of convergance of the GCD calculation, and the memory footprint *should* be comparable to that of conventional sieves (altho I haven't figured out yet a good approximation of the number of bits needed to store the results). Moreover, rather than requiring a buffer to mark off primes (as with conventional sieves), the memory is instead dedicated to some BigInteger type.
Anyway, I haven't yet tested the theory using my own BigInteger class, as I need to either determine the number of bits needed or else add the funtionality to the class to automatically "grow" as calculations proceed, but I am working on that. So I'd like to know what you guys think - is the idea worth pursuing? Also, if anyone knows of a decent "bits_needed" approximation function, please let me know. Thanks!
Oh, and here is a working example, in C++, using 32-bit unsigned int's (which, unfortunately, can only be used to generate all the primes up to 30!):
Code:
template < typename UnsignedInteger >
UnsignedInteger gcd( UnsignedInteger lhs, UnsignedInteger rhs )
{
for( ;; )
{
if( ( lhs %= rhs ) == 0 )
return rhs;
if( ( rhs %= lhs ) == 0 )
return lhs;
}
/*
We never really get here - this just prevents a compiler warning...
*/
return UnsignedInteger( );
}
template < typename UnsignedInteger, typename Iterator >
void generate_primes_up_to( UnsignedInteger const& val, Iterator out )
{
static UnsignedInteger const
one = 1;
for
(
UnsignedInteger
acc = 1,
idx = 2;
idx <= val;
++idx
)
{
if( gcd( acc, idx ) == one )
{
acc *= idx;
*out++ = idx;
}
}
}
#include <iostream>
#include <iterator>
int main( void )
{
using namespace
std;
unsigned
lim = 30;
generate_primes_up_to( lim, ostream_iterator< unsigned >( cout, "\n" ) );
}
One more thing - I realize that the generator function would be more efficient if it skipped even numbers, etc, but I chose to keep it simple, for the sake of clarity...