Idea for a fast and efficient prime sieve

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...

Code:

---

acc *= idx;

---

This, however, can make the value grow quite fast? What if I wanted to list the first million primes - wouldn't I have to deal with the product of million ever-growing values?

Otherwise it seems like a clever way to test if the given value is divisible by any of the primes found before.

Not sure if it can be called a sieve, though. It looks that fundamentally this is still based on trial divisions (finding GCD), except instead of many divisions with smaller values you'll have less divisions with greater values...

The result of your ongoing multiplication grows quickly initially (with a curve similar, if less steep, to the factorial function), but should slow down at very high numbers, if I understand correctly what the prime number theorem means. But it will definitely still grow quickly. For the sake of easy analysis, let's say it's O(n!) and disregard the lower density of prime numbers for high n. This is probably not algorithmically sound.
The number of bits needed for a number is log2(n). So the space required for your algorithm is O(log(n!)). I'm not sure if this can be reduced to a simpler term, but it is definitely greater than the O(n) of a conventional sieve.
But of course, if the n! is incorrect, the situation might be different.