Primality by Wilson's theorem: Difference between revisions
Content added Content deleted
(Added PL/I) |
(Added C++ solution) |
||
Line 493: | Line 493: | ||
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. The last performance figure illustrates that memoizing the factorials can help when calculating nearby prime numbers. |
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. The last performance figure illustrates that memoizing the factorials can help when calculating nearby prime numbers. |
||
=={{header|C++}}== |
|||
<lang cpp>#include <iomanip> |
|||
#include <iostream> |
|||
int factorial_mod(int n, int p) { |
|||
unsigned int f = 1; |
|||
for (; n > 0; --n) { |
|||
f = (f * n) % p; |
|||
if (f == 0) |
|||
break; |
|||
} |
|||
return f; |
|||
} |
|||
bool is_prime(int p) { |
|||
return p > 1 && factorial_mod(p - 1, p) == p - 1; |
|||
} |
|||
int main() { |
|||
std::cout << " n | prime?\n------------\n"; |
|||
std::cout << std::boolalpha; |
|||
for (int p : {2, 3, 9, 15, 29, 37, 47, 57, 67, 77, 87, 97, 237, 409, 659}) |
|||
std::cout << std::setw(3) << p << " | " << is_prime(p) << '\n'; |
|||
std::cout << "\nFirst 120 primes by Wilson's theorem:\n"; |
|||
int n = 0, p = 1; |
|||
for (; n < 120; ++p) { |
|||
if (is_prime(p)) |
|||
std::cout << std::setw(3) << p << (++n % 20 == 0 ? '\n' : ' '); |
|||
} |
|||
std::cout << "\n1000th through 1015th primes:\n"; |
|||
for (int i = 0; n < 1015; ++p) { |
|||
if (is_prime(p)) { |
|||
if (++n >= 1000) |
|||
std::cout << std::setw(4) << p << (++i % 16 == 0 ? '\n' : ' '); |
|||
} |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
n | prime? |
|||
------------ |
|||
2 | true |
|||
3 | true |
|||
9 | false |
|||
15 | false |
|||
29 | true |
|||
37 | true |
|||
47 | true |
|||
57 | false |
|||
67 | true |
|||
77 | false |
|||
87 | false |
|||
97 | true |
|||
237 | false |
|||
409 | true |
|||
659 | true |
|||
First 120 primes by Wilson's theorem: |
|||
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 |
|||
1000th through 1015th primes: |
|||
7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081 |
|||
</pre> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |