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. Ron Reeder 13 years, 7 months ago

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) 13 years, 7 months ago

Oh, whoops! I didn't catch that before. It should be fixed now. Created by Aaron Gallagher on Wed, 5 Dec 2007 (PSF)