Algorithms: Number Theory

int binary_gcd(int a, int b) {
    alg_require(((a >= 0) && (b >= 0)));
    if ((a == 0)) {
        return b;
    }
    if ((b == 0)) {
        return a;
    }
    int factor = 1;
    int temp = 0;
    while ((((a % 2) == 0) && ((b % 2) == 0))) {
        a = (a / 2);

    static int binary_gcd(int a, int b) {
        checked {
            alg_require(((a >= 0) && (b >= 0)));
            if ((a == 0)) {
                return b;
            }
            if ((b == 0)) {
                return a;
            }
            int factor = 1;
            int temp = 0;
            while ((((a % 2) == 0) && ((b % 2) == 0))) {

function binary_gcd(int $a, int $b): int {
    alg_require((($a >= 0) && ($b >= 0)));
    if (($a == 0)) {
        return $b;
    }
    if (($b == 0)) {
        return $a;
    }
    $factor = 1;
    $temp = 0;
    while (((($a % 2) == 0) && (($b % 2) == 0))) {
        $a = intdiv($a, 2);

    static int is_prime(int n) {
        checked {
            if ((n < 2)) {
                return 0;
            }
            if ((n == 2)) {
                return 1;
            }
            if (((n % 2) == 0)) {
                return 0;
            }
            int d = 3;

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);
        }
    }