Anonymous user
Miller–Rabin primality test: Difference between revisions
m
{{out}} / -Category:Scala Implementations
No edit summary |
m ({{out}} / -Category:Scala Implementations) |
||
Line 1:
{{task|Prime Numbers}}{{Wikipedia|Miller–Rabin primality test}}
The [[wp:Miller–Rabin primality test|Miller–Rabin primality test]] or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime or not
The algorithm, as modified by [[wp:Michael O. Rabin|Michael O. Rabin]] to avoid the [[wp:generalized Riemann hypothesis|generalized Riemann hypothesis]], is a probabilistic algorithm.
The pseudocode, from [[wp:Miller-Rabin primality test#Algorithm_and_running_time|Wikipedia]] is:
Line 25 ⟶ 28:
===ordinary integers===
It's easy to get overflows doing exponential calculations.
Therefore I implemented my own function for that.
For Number types >= 2**64 you may have to use an external library -- see below.
First, a package Miller_Rabin is specified.
The same package is used elsewhere in Rosetta Code,
such as for the [[Carmichael 3 strong pseudoprimes]] the [[Extensible prime generator]], and the [[Emirp primes]].
<lang Ada>generic
Line 224 ⟶ 230:
end Miller_Rabin;</lang>
{{out}}
<pre>Prime(4547337172376300111955330758342147474062293202868155909489)=TRUE
Prime(4547337172376300111955330758342147474062293202868155909393)=FALSE</pre>
Line 495 ⟶ 501:
& out$!last
);</lang>
{{out}}
<pre>937 941 947 953 967 971 977 983 991 997</pre>
=={{header|C}}==
{{libheader|GMP}}
Line 507 ⟶ 514:
'''miller-rabin.c'''
{{trans|Fortran}}
For <code>decompose</code> (and header <tt>primedecompose.h</tt>),
see [[Prime decomposition#C|Prime decomposition]].
<lang c>#include <stdbool.h>
#include <gmp.h>
Line 2,390 ⟶ 2,398:
: with a K ≥ 3, rare as hen's teeth.
This would be in the same vein as:
3 is prime, 5 is prime, 7 is prime, all odd numbers are prime.
<lang rexx>/*REXX program puts the Miller-Rabin primality test through its paces.*/
parse arg limit accur . /*get some optional arguments*/
Line 2,453 ⟶ 2,462:
end /*j*/ /*this comment not left blank. */
return /*whew! All done with the primes*/</lang>
<pre style="height:30ex">
There are 1229 primes ≤ 10000
Line 2,576 ⟶ 2,585:
=={{header|Scala}}==
{{libheader|Scala}}<lang scala>import scala.math.BigInt
| |||