Rosetta Code

Sieve of Pritchard: Difference between revisions

Page Discussion

Sieve of Pritchard (view source)

Revision as of 06:58, 7 September 2022

909 bytes added ,  1 year ago
→‎{{header|C#|CSharp}}: added add/remove stats
(→‎{{header|C#|CSharp}}: added add/remove stats)
Line 121:
 
Compared to the prototype algorithm, it appears there isn't any code to do the follow-up end-of-wheel additions when necessary. But the main loop limit has been changed to go to the next prime, and the existing code handles the additions.
 
Updated to include "numbers added / removed (to / from ''members'')" and performance statistics. The "removed" figure includes both composite numbers and prime numbers less than the square root of ''limit''. The Wikipedia article indicates only eight removals (for ''limit'' = 150) because it doesn't count the removed primes and the initial ''1'' that the ''members'' array is initialized with.
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
Line 127 ⟶ 129:
 
// Returns list of primes up to limit using Pritchard (wheel) sieve
static List<int> PrimesUpTo(int limit, bool verbose = false) {
var sw = System.Diagnostics.Stopwatch.StartNew();
var members = new SortedSet<int>{ 1 };
int stp = 1, prime = 2, n, nxtpr, rtlim = 1 + (int)Math.Sqrt(limit), nl, ac = 2, rc = 1;
varList<int> primes = new List<int>(), tl = new List<int>();
while (prime <= rtlim) {
nl = Math.Min(limit, prime * stp, limit);▼
if (stp < limit) {
var nu = new List<int>tl.Clear();
foreach (var w in members)
for (n = w + stp; n <= nl; n += stp) nutl.Add(n);
members.UnionWith(nutl); ac += tl.Count;
}
stp = nl; // update wheel size to wheel limit
nxtpr = 05; // for obtaining the next prime
var wb = new List<int>tl.Clear();
foreach (var w in members) {
if (nxtpr == 05 && w > prime) nxtpr = w;
if (members.Contains(n = prime * w) > nl) wbbreak; else tl.Add(n);
}
foreach (var itm in wbtl) members.Remove(itm); rc += tl.Count;
primes.Add(prime);
prime = prime == 2 ? 3 : nxtpr;
▲ nl = Math.Min(limit, prime * stp);
}
members.Remove(1); primes.AddRange(members); sw.Stop();
if (verbose) Console.WriteLine("Up to {0}, added:{1}, removed:{2}, primes counted:{3}, time:{4} ms", limit, ac, rc, primes.Count, sw.Elapsed.TotalMilliseconds);
primes.AddRange(members);
return primes;
}
 
static void Main(string[] args) {
Console.WriteLine("[{0}]", string.Join(", ", PrimesUpTo(150, true)));
PrimesUpTo(1000000, true);
}
}</syntaxhighlight>
{{out}}Timing from Tio.run:
<pre>Up to 150, added:45, removed:14, primes counted:35, time:13.2842 ms
<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149]</pre>
Up to 1000000, added:186825, removed:108494, primes counted:78498, time:139.4323 ms
</pre>
 
=={{header|J}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/329748"