Welcome, guest | Sign In | My Account | Store | Cart

Two simple generators for generating prime numbers using a prime sieve. gen_sieve(n) will produce all prime numbers

isprime is an example of how one could use gen_sieve: a quick function for testing primality by attempting modulo division with each potential prime factor of a number.

Python, 29 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import math

def gen_sieve(ceiling=None):
    if ceiling is not None:
        if ceiling % 2 == 0:
            ceiling -= 1
        highest_prime = math.ceil(math.sqrt(ceiling))
    last_val = 1
    found_primes = []
    yield 2
    while ceiling is None or ceiling > last_val:
        current_val = None
        while current_val is None:
            current_val = last_val = last_val + 2
            for prime, square in found_primes:
                if current_val < square: 
                    break
                if current_val % prime == 0:
                    current_val = None
                    break
        yield current_val
        if ceiling is None or highest_prime > last_val:
            found_primes.append((current_val, current_val ** 2))

def isprime(n):
    for fac in gen_sieve(int(math.ceil(math.sqrt(n)))):
        if n % fac == 0 and n != fac:
            return fac
    return 0

This is the fastest prime sieve I could come up with in python. There might be a way to reduce the memory footprint.

2 comments

Ron Reeder 16 years ago  # | flag

2 is prime. 2 is a prime number... Your algorithm says it's not.

I ran it using the following code:

def main(): testnos = (1,2,3,4,5,6,7,8,9,10,11,12,13,41) for testno in testnos: factor = isprime(testno) if factor: print ("Number is not prime: %i - factor is: %i\n" % (testno,factor)) else: print ("Prime Number! - %i\n" % testno) if __name__ == '__main__': main()

Output: Prime Number! - 1

Number is not prime: 2 - factor is: 2

Prime Number! - 3

Number is not prime: 4 - factor is: 2

Prime Number! - 5 ...

Aaron Gallagher (author) 15 years, 12 months ago  # | flag

Oh, whoops! I didn't catch that before. It should be fixed now.

Created by Aaron Gallagher on Wed, 5 Dec 2007 (PSF)
Python recipes (4591)
Aaron Gallagher's recipes (3)

Required Modules

Other Information and Tasks