Primality by Wilson's theorem: Difference between revisions
Added C# version w/ performance comparison to Sieve of Eratosthenes
m (→{{header|Factor}}: remove unused vocab) |
(Added C# version w/ performance comparison to Sieve of Eratosthenes) |
||
Line 77:
Is 20 prime: 0
Is 21 prime: 0</pre>
=={{header|C#|Csharp}}==
{{libheader|System.Numerics}}
Performance comparison to Sieve of Eratosthenes.
<lang csharp>using System;
using System.Linq;
using System.Collections;
using static System.Console;
using System.Collections.Generic;
using BI = System.Numerics.BigInteger;
class Program {
// initialization
const int fst = 120, skp = 1000, max = 1015; static double et1, et2; static DateTime st;
static string ms1 = "Wilson's theorem method", ms2 = "Sieve of Eratosthenes method",
fmt = "--- {0} ---\n\nThe first {1} primes are:", fm2 = "{0} prime thru the {1} prime:";
static List<int> lst = new List<int>();
// dumps a chunk of the prime list (lst)
static void Dump(int s, int t, string f) {
foreach (var item in lst.Skip(s).Take(t)) Write(f, item); WriteLine("\n"); }
// returns the cardinal string representation of a number
static string Card(int x, string fmt = "{0:n0}") { return string.Format(fmt, x) +
"thstndrdthththththth".Substring((x % 10) << 1, 2); }
// shows the results of one type of prime tabulation
static void ShowOne(string title, ref double et) {
WriteLine(fmt, title, fst); Dump(0, fst, "{0,3} ");
WriteLine(fm2, Card(skp), Card(max)); Dump(skp - 1, max - skp + 1, "{0,4} ");
WriteLine("Time taken: {0}ms\n", et = (DateTime.Now - st).TotalMilliseconds); }
// for stand-alone computation
static BI factorial(BI n) { BI res = 1; if (n < 2) return res;
for (; n > 0; n--) res *= n; return res; }
static bool WTisPrime(BI n) { return ((factorial(n - 1) + 1) % n) == 0; }
// end stand-alone
static void Main(string[] args) { st = DateTime.Now;
BI f = 1; for (int n = 2; lst.Count < max; f *= n++) if ((f + 1) % n == 0) lst.Add(n);
ShowOne(ms1, ref et1);
st = DateTime.Now; int lmt = lst.Last(); lst.Clear(); BitArray flags = new BitArray(lmt + 1);
for (int n = 2; n <= lmt; n++) if (!flags[n]) {
lst.Add(n); for (int k = n * n; k <= lmt; k += n) flags[k] = true; }
ShowOne(ms2, ref et2); st = DateTime.Now;
WriteLine("{0} was {1:0.0} times slower than the {2}.", ms1, et1 / et2, ms2);
// stand-alone computation
WriteLine("\n" + ms1 + " stand-alone computation:");
for (BI x = lst[skp - 1]; x <= lst[max - 1]; x++) if (WTisPrime(x)) Write("{0,4} ", x);
WriteLine(); WriteLine("\nTime taken: {0}ms\n", (DateTime.Now - st).TotalMilliseconds);
}
}</lang>
{{out}}
<pre style="white-space: pre-wrap;">--- Wilson's theorem method ---
The first 120 primes are:
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 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659
1,000th prime thru the 1,015th prime:
7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081
Time taken: 164.7332ms
--- Sieve of Eratosthenes method ---
The first 120 primes are:
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 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659
1,000th prime thru the 1,015th prime:
7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081
Time taken: 4.6169ms
Wilson's theorem method was 35.7 times slower than the Sieve of Eratosthenes method.
Wilson's theorem method stand-alone computation:
7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081
Time taken: 2727.164ms</pre>
The "slow" factor may be different on different processors and programming environments. For example, on Tio.run, the "slow" factor is anywhere between 120 and 180 times slower. Slowness most likely caused by the sluggish BigInteger library usage. The SoE method, although quicker, does consume some memory (due to the ''flags'' BitArray). The Wilson's theorem method may consume considerable memory due to the large factorials (the ''f'' variable) when computing larger primes.
The Wilson's theorem method is better suited for computing single primes, as the SoE method causes one to compute all the primes up to the desired item. In this C# implementation, a running factorial is maintained to help the Wilson's theorem method be a little more efficient. The stand-alone results show that when having to compute a BigInteger factorial for every primality test, the performance drops off considerably more.
=={{header|Erlang}}==
| |||