Ceasar's Mind

Follow me: @Ceasar_Bautista

The Quadratic Sieve

with 3 comments

Just got done with a terrible day of magic numbers. To spare everyone the trouble, here’s a fairly clear version of a quadratic sieve for generating prime numbers that ought to be self-explanatory and easily modified– as opposed to many other algorithms out there.

def primes(n):
    '''Get all primes up to n.'''
    n = int(n)
    if n < 2:
        return []
    sieve = range(n)
    sieve[1] = 0
    root = n ** 0.5
    index = 0
    while index <= root:
        if sieve[index]:
            i = index ** 2
            while i &lt; n:
                sieve[i] = 0
                i += index
        index += 1
    return [x for x in sieve if x]

Written by Ceasar Bautista

2011/07/10 at 02:49

Posted in Uncategorized

Tagged with , ,

3 Responses

Subscribe to comments with RSS.

  1. This is NOT a quadratic sieve but the sieve of eratosthenes.


    2013/12/14 at 11:20

    • Actually, it is. Note line 12.

      Ceasar Bautista

      2013/12/23 at 13:35

  2. I agree with zobytwo, this is not Quadratic Sieve, so you need more documentation before post this.
    Quadratic sieves factorizes integers not shows the primes ‘up to’ n number as you say.


    2014/01/30 at 06:55


Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s