Sieve of Pritchard: Difference between revisions

Content added Content deleted

Inline

@@ Line 185: / Line 185: @@
     while prime * prime <= limit:
         if steplength < limit:
+            nlimit = min(prime * steplength, limit)
             for w in list(members):
                 n = w + steplength
-                while n <= max(prime * steplength, limit):
+                while n <= nlimit:
                     members.add(n)
                     n += steplength
-            steplength = min(prime * steplength, limit)
+            steplength = nlimit
         for w in sorted(members):
             n = prime * w
-            if n in members:
+            if n > steplength: break # no use trying to remove items that can't even be there
-                members.remove(n)
+            members.remove(n) # no checking necessary now
         primes.append(prime)
         prime = 3 if prime == 2 else min(m for m in members if m > 1)
     if steplength < limit:
-        for w in list(members):
+        for w in sorted(members):
             n = w + steplength
+            if n > limit: break # no use etc...
             while n <= limit:
                 members.add(n)
                 n += steplength
+    return primes + sorted(members)[1:]
-        steplength = limit
-    primes += [m for m in members if m != 1]
-    return sorted(p for p in primes if p <= limit)
 print(pritchard(150))