How to find out if two numbers are relatively prime?

Question

I'm trying to write a method that will calculate if two numbers are relatively prime for an assignment. I'm primarily looking for answers on where to start. I know there is a method gcd() that will do a lot of it for me, but the assignment is pretty much making me do it without gcd or arrays.

I kind of have it started, because I know that I will have to use the % operator in a for loop.

public static boolean relativeNumber(int input4, int input5){
    for(int i = 1; i <= input4; i++)

Obviously this method is only going to return true or false because the main function is only going to print a specific line depending on if the two numbers are relatively prime or not.

I'm thinking I will probably have to write two for loops, both for input4, and input5, and possibly some kind of if statement with a logical && operand, but I'm not sure.

Answer 1

Well in case they are relatively prime, the greatest common divider is one, because - if otherwise - both numbers could be devided by that number. So we only need an algorithm to calculate the greatest common divider, for instance Euclid's method:

private static int gcd(int a, int b) {
    int t;
    while(b != 0){
        t = a;
        a = b;
        b = t%b;
    }
    return a;
}

And then:

private static boolean relativelyPrime(int a, int b) {
    return gcd(a,b) == 1;
}

Euclid's algorithm works in O(log n) which thus is way faster than enumerating over all potential divisors which can be optimized to O(sqrt n).

Answer 2

Swift 4 code for @williem-van-onsem answer;

func gcd(a: Int, b: Int) -> Int {
    var b = b
    var a = a
    var t: Int!

    while(b != 0){
        t = a;
        a = b;
        b = t%b;
    }
    return a
}

func relativelyPrime(a : Int, b: Int) -> Bool{
    return gcd(a: a, b: b) == 1
}

Usage;

print(relativelyPrime(a: 2, b: 4)) // false