Implement Sieve of Eratosthenes with unit tests

lcheung90 · lcheung90 · commit 3753953f0d9f · 2013-04-18T13:39:34.000-07:00
diff --git a/algorithms/math/sieve_eratosthenes.py b/algorithms/math/sieve_eratosthenes.py
@@ -0,0 +1,32 @@
+"""
+    sieve_eratosthenes.py
+
+    Implementation of the Sieve of Eratosthenes algorithm.
+
+    Depth First Search Overview:
+    ------------------------
+    Is a simple, ancient algorithm for finding all prime numbers 
+    up to any given limit. It does so by iteratively marking as composite (i.e. not prime) 
+    the multiples of each prime, starting with the multiples of 2.
+
+    The sieve of Eratosthenes is one of the most efficient ways 
+    to find all of the smaller primes (below 10 million or so).
+
+    Time Complexity: O(n log log n)
+
+    Pseudocode: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes    
+"""
+
+def eratosthenes(end,start=2):
+    if start < 2:
+        start = 2
+    primes = range(start,end)
+    marker = 2
+    while marker < end:
+        for i in xrange(marker, end+1):
+            if marker*i in primes:
+                primes.remove(marker*i)
+        marker += 1
+    return primes
+        
+    
diff --git a/algorithms/tests/test_math.py b/algorithms/tests/test_math.py
@@ -1,5 +1,6 @@
 import unittest
 from ..math.extended_gcd import extended_gcd
+from ..math.sieve_eratosthenes import eratosthenes
 
 
 class TestExtendedGCD(unittest.TestCase):
@@ -24,3 +25,15 @@ def test_extended_gcd(self):
         # Find extended_gcd of 50 and 15
         (a, b) = extended_gcd(50, 15)
         self.assertIs(50 * a + 15 * b, 5)
+
+class TestSieveOfEratosthenes(unittest.TestCase):
+
+    def test_eratosthenes(self):
+        rv1 = eratosthenes(-10)
+        rv2 = eratosthenes(10)
+        rv3 = eratosthenes(100,5)
+        rv4 = eratosthenes(100,-10)
+        self.assertEqual(rv1,[])
+        self.assertEqual(rv2,[2, 3, 5, 7])
+        self.assertEqual(rv3,[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])
+        self.assertEqual(rv4,[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])
