Divisors.java

/* *****************************************************************************
 *  Name:              Ada Lovelace
 *  Coursera User ID:  123456
 *  Last modified:     October 16, 1842
 **************************************************************************** */

public class Divisors {
    // Returns the greatest common divisor of a and b.
    public static int gcd(int ax, int bx) {
        int a = Math.max(Math.abs(ax), Math.abs(bx));
        int b = Math.min(Math.abs(ax), Math.abs(bx));
        int x, r;
        if (a == 0 && b != 0) r = b;
        else if (a != 0 && b == 0) r = a;
        else if (a == 0) r = 0;
        else {
            do {
                x = a;
                a = b;
                r = a;
                b = x % b;
            } while (b != 0);
        }
        return r;
    }

    // Returns the least common multiple of a and b.
    public static int lcm(int a, int b) {
        if (a == 0 || b == 0) return 0;
        else return (Math.abs(a) / gcd(a, b)) * Math.abs(b);
    }

    // Returns true if a and b are relatively prime; false otherwise.
    public static boolean areRelativelyPrime(int a, int b) {
        if (gcd(a, b) == 1) return true;
        else return false;
    }

    // Returns the number of integers between 1 and n that are
    // relatively prime with n.
    public static int totient(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (areRelativelyPrime(n, i)) {
                count++;
            }
        }
        return count;
    }

    // Takes two integer command-line arguments a and b
    public static void main(String[] args) {
        int a = Integer.parseInt(args[0]);
        int b = Integer.parseInt(args[1]);
        StdOut.println("gcd(" + a + "," + b + ") = " + gcd(a, b));
        StdOut.println("lcm(" + a + "," + b + ") = " + lcm(a, b));
        StdOut.println("areRelativelyPrime(" + a + "," + b + ") = " + areRelativelyPrime(a, b));
        StdOut.println("totient(" + a + ") = " + totient(a));
        StdOut.println("totient(" + b + ") = " + totient(b));
    }
}