Sieve of Pritchard: Difference between revisions
→C#: Limit on wheel expansion was incorrect. Old version had proper output, but went about it in the wrong way.
(→{{header|J}}: work around some details of J's historical implementation of sparse arrays to better match the spirit of this sieve) |
(→C#: Limit on wheel expansion was incorrect. Old version had proper output, but went about it in the wrong way.) |
||
Line 28:
=={{header|C#|CSharp}}==
Loosely based on the Python version. I cut a couple of things out and it still worked. Not too crazy about having to create temporary lists to add or remove from the
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
Line 36:
// Returns list of primes up to limit using Pritchard (wheel) sieve
static List<int> PrimesUpTo(int limit) {
var members = new
int stp = 1, prime = 2, n,
var primes = new List<int>();
while (prime <= rtlim) {
if (stp < limit) {
var nu = new List<int>();
foreach (var w in members)
for (n = w + stp; n <= nl; n += stp) nu.Add(n);
members.UnionWith(nu);
}
stp = Math.Min(prime * stp, limit);
var wb = new List<int>();
foreach (var w in members) {
if (
if (members.Contains(n = prime * w)) wb.Add(n);
}
foreach (var itm in wb
primes.Add(prime);
prime = prime == 2 ? 3 :
nl = Math.Min(limit, prime * stp);
}
members.Remove(1);
|