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
Download
Copy to clipboard1 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.
Tags: algorithms
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 ...
Oh, whoops! I didn't catch that before. It should be fixed now.