Free Photos
WordPress Themes

Better Sieve

#!/usr/bin/env python # Sieve of Eratosthenes - to find all the prime numbers in range 1 to n # http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes # Optimized by only putting in 2, 3 & numbers of the form 6n+/-1 in the initial list. def better_sieve(n): primes = [] numbers = [] if 2<=n: primes.append(2) if 3<=n: primes.append(3) for i in range(1, n/6 +1): numbers.append(6*i-1) numbers.append(6*i+1) while numbers: primes.append(numbers.pop(0)) for e in numbers: if not e%primes[-1]: numbers.pop(numbers.index(e)) return primes def is_prime(n): prime_list = better_sieve(n) if n in prime_list: return True return False
Optimized the Sieve of Eratosthenes a little by only putting in 2, 3 & numbers of the form 6n+/-1 in the initial list

Be the first to comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.