Algorithms: Number Theory

function power(int $base, int $exponent): int {
    alg_require(($exponent >= 0));
    $result = 1;
    while (($exponent > 0)) {
        if ((($exponent % 2) == 1)) {
            $result = alg_mul($result, $base);
        }
        $exponent = intdiv($exponent, 2);
        if (($exponent > 0)) {
            $base = alg_mul($base, $base);
        }
    }

function is_prime(int $n): int {
    if (($n < 2)) {
        return 0;
    }
    if (($n == 2)) {
        return 1;
    }
    if ((($n % 2) == 0)) {
        return 0;
    }
    $d = 3;
    while (($d <= intdiv($n, $d))) {

    static int modular_power(int base, int exponent, int modulus) {
        alg_require(((base >= 0) && (exponent >= 0) && (modulus > 0) && (modulus <= 46340)));
        int result = (1 % modulus);
        base = (base % modulus);
        while ((exponent > 0)) {
            if (((exponent % 2) == 1)) {
                result = (Math.multiplyExact(result, base) % modulus);
            }
            base = (Math.multiplyExact(base, base) % modulus);
            exponent = (exponent / 2);
        }
        return result;

    static int lcm(int a, int b) {
        alg_require(((a >= 0) && (b >= 0)));
        if (((a == 0) || (b == 0))) {
            return 0;
        }
        int x = a;
        int y = b;
        int remainder = 0;
        while ((y != 0)) {
            remainder = (x % y);
            x = y;
            y = remainder;

    static int gcd(int a, int b) {
        alg_require(((a >= 0) && (b >= 0)));
        int remainder = 0;
        while ((b != 0)) {
            remainder = (a % b);
            a = b;
            b = remainder;
        }
        return a;
    }

    public static void main(String[] args) {