Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (→{{header|Sidef}}: minor simplifications) |
(Added Kotlin) |
||
Line 2,275: | Line 2,275: | ||
end |
end |
||
</lang> |
</lang> |
||
=={{header|Kotlin}}== |
|||
Translating the pseudo-code directly rather than using the Java library method BigInteger.isProbablePrime(certainty): |
|||
<lang scala>// version 1.1.1 |
|||
import java.math.BigInteger |
|||
import java.util.Random |
|||
val bigTwo = BigInteger.valueOf(2L) |
|||
fun isProbablyPrime(n: BigInteger, k: Int): Boolean { |
|||
require (n > bigTwo && n % bigTwo == BigInteger.ONE) { "Must be odd and greater than 2" } |
|||
var s = 0 |
|||
val nn = n - BigInteger.ONE |
|||
var d: BigInteger |
|||
do { |
|||
s++ |
|||
d = nn.shiftRight(s) |
|||
} |
|||
while (d % bigTwo == BigInteger.ZERO) |
|||
val rand = Random() |
|||
loop@ for (i in 1..k) { |
|||
var a: BigInteger |
|||
do { |
|||
a = BigInteger(n.bitLength(), rand) |
|||
} |
|||
while(a < bigTwo || a > nn) // make sure it's in the interval [2, n - 1] |
|||
var x = a.modPow(d, n) |
|||
if (x == BigInteger.ONE || x == nn) continue |
|||
for (r in 1 until s) { |
|||
x = (x * x) % n |
|||
if (x == BigInteger.ONE) return false |
|||
if (x == nn) break@loop |
|||
} |
|||
return false |
|||
} |
|||
return true |
|||
} |
|||
fun main(args: Array<String>) { |
|||
val k = 20 // say |
|||
// obtain all primes up to 100 |
|||
println("The following numbers less than 100 are prime:") |
|||
for (i in 3..99 step 2) |
|||
if (isProbablyPrime(BigInteger.valueOf(i.toLong()), k)) print("$i ") |
|||
println("\n") |
|||
// check if some big numbers are probably prime |
|||
val bia = arrayOf( |
|||
BigInteger("4547337172376300111955330758342147474062293202868155909489"), |
|||
BigInteger("4547337172376300111955330758342147474062293202868155909393") |
|||
) |
|||
for (bi in bia) |
|||
println("$bi is ${if (isProbablyPrime(bi, k)) "probably prime" else "composite"}") |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
The following numbers less than 100 are prime: |
|||
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
|||
4547337172376300111955330758342147474062293202868155909489 is probably prime |
|||
4547337172376300111955330758342147474062293202868155909393 is composite |
|||
</pre> |
|||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |