#!/usr/bin/ruby

#
## https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test
#

func is_prime(n { .is_odd && (_ > 2) }, k) {
    var s = 0
    var d = n.dec
    (d >>= 1; ++s) while d.is_even

    k.times {
        var a = irand(2, n-1)
        var x = expmod(a, d, n)
        next if (x ~~ [1, n-1])

        (s-1).times {
            x.expmod!(2, n)
            return false if x.is_one
            break if (x == n-1)
        }
        return false if (x != n-1)
    }

    return true
}

func is_prime((2), _k) { true }
func is_prime(_n, _k)  { false }

var numbers = [
    61_794_479,
    2867561004669023153611,
    803_086_491,
    171_659_461_843,
    902_802_468_593,
    3_539_679_283_117,
    12_905_496_217_051,
    103_497_586_783_721,
];

numbers.each { |n|
    var p = is_prime(n, 12);
    say ("#{n} is" + (p ? ' ' : ' NOT ') + 'prime');
    assert_eq(p, n.is_prime);
}

var p = gather {
    for n in (1..100) {
        is_prime(n, 10) && take(n)
    }
}

assert_eq(p, primes(100))