Summation of primes: Difference between revisions

Content added Content deleted

Inline

@@ Line 414: / Line 414: @@
 <lang python>'''Summatiom of primes'''
-from itertools import takewhile
+from itertools import count, takewhile
@@ Line 433: / Line 433: @@
 # ----------------------- GENERIC ------------------------
+# enumFromThen :: Int -> Int -> [Int]
+def enumFromThen(m):
+    '''A non-finite stream of integers
+       starting at m, and continuing
+       at the interval between m and n.
+    '''
+    return lambda n: count(m, n - m)
 # primes :: [Int]
 def primes():
-    ''' Non finite sequence of prime numbers.
+    '''An infinite stream of primes.'''
-    '''
+    seen = {}
-    n = 2
+    yield 2
-    dct = {}
+    p = None
+    for q in enumFromThen(3)(5):
-    while True:
-        if n in dct:
+        p = seen.pop(q, None)
-            for p in dct[n]:
+        if p is None:
-                dct.setdefault(n + p, []).append(p)
+            seen[q ** 2] = q
-            del dct[n]
+            yield q
         else:
-            yield n
+            seen[
-            dct[n * n] = [n]
+                until(
-        n = 1 + n
+                    lambda x: x not in seen,
+                    lambda x: x + 2 * p,
+                    q + 2 * p
+                )
+            ] = p
+# until :: (a -> Bool) -> (a -> a) -> a -> a
+def until(p, f, v):
+    '''The result of repeatedly applying f until p holds.
+       The initial seed value is x.
+    '''
+    while not p(v):
+        v = f(v)
+    return v