Anonymous user
Miller–Rabin primality test: Difference between revisions
add Tcl
(smalltalk) |
(add Tcl) |
||
Line 323:
(n millerRabinTest: 10) ifTrue: [ n printNl ]
].</lang>
=={{header|Tcl}}==
Use Tcl 8.5 for large integer support
<lang tcl>package require Tcl 8.5
proc miller_rabin {n k} {
if {$n <= 3} {return true}
if {$n % 2 == 0} {return false}
# write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1
set d [expr {$n - 1}]
set s 0
while {$d % 2 == 0} {
set d [expr {$d / 2}]
incr s
}
# LOOP
while {$k > 0} {
incr k -1
set a [expr {2 + int(rand()*($n - 4))}]
set x [expr {($a ** $d) % $n}]
if {$x == 1 || $x == $n - 1} {
# do next LOOP
continue
}
set do_next_loop false
for {set r 1} {$r < $s} {incr r} {
set x [expr {($x ** 2) % $n}]
if {$x == 1} {return false}
if {$x == $n - 1} {
# do next LOOP
# Tcl can't directly control the outer loop from the inner loop
set do_next_loop true
break
}
}
if {$do_next_loop} continue
return false
}
return true
}
for {set i 1} {$i < 1000} {incr i} {
if {[miller_rabin $i 10]} {
puts $i
}
}</lang>
produces
<pre>1
2
3
5
7
11
...
977
983
991
997</pre>
| |||