Sieve of Pritchard: Difference between revisions

Content added Content deleted

Inline

@@ Line 40: / Line 40: @@
         var primes = new List<int>();
         while (prime <= rtlim) {
-            if (stp < limit)
+            if (stp < limit) {
-                foreach (var w in new List<int>(members)) {
+                var nu = new List<int>();
+                foreach (var w in members) {
                     n = w + stp;
-                    while (n <= limit) { members.Add(n); n += stp; }
+                    while (n <= limit) { nu.Add(n); n += stp; }
                 }
-                stp = Math.Min(prime * stp, limit);
+                members.UnionWith(nu);
+            }
+            stp = Math.Min(prime * stp, limit);
             np = 0;
-            foreach (var w in new List<int>(members)) {
+            var wb = new List<int>();
+            foreach (var w in members) {
                 if (np == 0 && w > prime) np = w; // next prime
-                if (members.Contains(n = prime * w)) members.Remove(n);
+                if (members.Contains(n = prime * w)) wb.Add(n);
             }
+            foreach (var itm in wb) if (members.Contains(itm)) members.Remove(itm);
             primes.Add(prime);
             prime = prime == 2 ? 3 : np;
@@ Line 60: / Line 65: @@
     static void Main(string[] args) {
-        Console.WriteLine("[" + string.Join(", ", PrimesUpTo(150)) + "]");
+        Console.WriteLine("[{0}]", string.Join(", ", PrimesUpTo(10000)));
     }
 }</syntaxhighlight>