From acc8a7677ff573cf2e3b617f717034626cba1da9 Mon Sep 17 00:00:00 2001 From: Reiner Herrmann Date: Fri, 19 Mar 2010 20:18:47 +0100 Subject: added module for common operations (like prime sieve) --- src/projecteuler/common.py | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 src/projecteuler/common.py diff --git a/src/projecteuler/common.py b/src/projecteuler/common.py new file mode 100644 index 0000000..dafed9c --- /dev/null +++ b/src/projecteuler/common.py @@ -0,0 +1,32 @@ + +class sieve: + limit = 100 + + def __init__(self, limit): + self.limit = limit + self.number_list = [False] + [True]*(self.limit-1) + self.list_len = len(self.number_list) + + def next_prime(self, i): + x = i+1 + while(x <= self.list_len): + if self.number_list[x-1] == True: + break + x += 1 + return x + + def primes(self): + i = 2 + while(i*i <= self.list_len): + x = i*i + while(x <= self.list_len): + self.number_list[x-1] = False + x += i + i = self.next_prime(i) + + primeset = set() + for i in xrange(1, self.limit+1): + if self.number_list[i-1]: + primeset.add(i) + return primeset + -- cgit v1.2.3