## 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 < n: sieve[i] = 0 i += index index += 1 return [x for x in sieve if x]

Advertisements

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

zobytwo2013/12/14 at 11:20

Actually, it is. Note line 12.

Ceasar Bautista2013/12/23 at 13:35

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.

Warrior2014/01/30 at 06:55