Sieve of Pritchard: Difference between revisions

Line 25:

*   [[partition an integer X into N primes]]

*   [[sequence of primes by Trial Division]]

=={{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 HashSet, seems inefficient. But that is the work-around I employed, since HashSets can't be accessed by indexing. I haven't yet directly tested this against a Sieve of Eratosthenes to compare performance.

<syntaxhighlight lang=csharp>using System;

using System.Collections.Generic;

class Program {

// Returns list of primes up to limit using Pritchard (wheel) sieve

static List<int> PrimesUpTo(int limit) {

var members = new HashSet<int>{ 1 };

int stp = 1, prime = 2, n, np, rtlim = 1 + (int)Math.Sqrt(limit);

var primes = new List<int>();

while (prime <= rtlim) {

if (stp < limit)

foreach (var w in new List<int>(members)) {

n = w + stp;

while (n <= limit) { members.Add(n); n += stp; }

}

stp = Math.Min(prime * stp, limit);

np = 0;

foreach (var w in new List<int>(members)) {

if (np == 0 && w > prime) np = w; // next prime

if (members.Contains(n = prime * w)) members.Remove(n);

}

primes.Add(prime);

prime = prime == 2 ? 3 : np;

}

members.Remove(1);

primes.AddRange(members);

return primes;

}

static void Main(string[] args) {

Console.WriteLine("[" + string.Join(", ", PrimesUpTo(150)) + "]");

}

}</syntaxhighlight>

=={{header|J}}==