# Ceasar's Mind

## The Quadratic Sieve

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

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

zobytwo

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.

Warrior

2014/01/30 at 06:55