Thread: Idea for a fast and efficient prime sieve

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Waterloo, Texas

    Lightbulb 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!):

    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;
                acc = 1, 
                idx = 2;
            idx <= val;
            if( gcd( acc, idx ) == one )
                acc *= idx;
                *out++ = idx;
    #include <iostream>
    #include <iterator>
    int main( void )
        using namespace 
            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...
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
        return std::pow
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;

  2. #2
    The larch
    Join Date
    May 2006
    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...
    Last edited by anon; 06-20-2010 at 05:50 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    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.
    All the buzzt!

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed