gistfile1.tcl

proc prime? n {
    if {$n <= 0} { return 0 }
    if {$n >= 341550071728321} { error prime? }
    if {$n < 4759123141} { set as {2 7 61} } else { set as {2 3 5 7 11 13 17} }
    if {$n == 2 || $n == 3 || $n == 5 || $n == 7 || $n == 11 || $n == 13 || $n == 17 || $n == 61} {
        return 1
    }
    if {$n == 1 || $n % 2 == 0} { return 0 }
    set d [expr {$n - 1}]
    while {$d % 2 == 0} { set d [expr {$d / 2}] }
    foreach a $as {
        set t $d
        set y [modpow $a $t $n]
        while {$t != $n-1 && $y != 1 && $y != $n-1} {
            set y [expr {$y * $y % $n}]
            set t [expr {$t * 2}]
        }
        if {$y != $n-1 && $t % 2 == 0} { return 0 }
    }
    return 1
}

proc modpow {b e m} {
    set result 1
    while {$e > 0} {
        if {$e % 2 == 1} { set result [expr {$result * $b % $m}] }
        set e [expr {$e / 2}]
        set b [expr {$b * $b % $m}]
    }
    return $result
}