Last Updated: 12 Jul, 2020
Check If Given Numbers Are Coprime
Easy
You have been given two numbers 'a' and 'b'. Write a function that checks if the given numbers are co-prime.
Input format :
The first line contains an Integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first and only line of each test case or query contains two single space separated numbers 'a' and 'b'.
Output Format :
For each test case, print 'true' if the numbers are co-prime and 'false' otherwise.
Output for every test case will be printed in a separate line.
Note :
Your are only required to return a boolean value. No need to print anything.
Constraints :
1 <= t <= 10^4
1 <= A <= 10^15
1 <= B <= 10^15
where 't' is the number of test cases, 'A' and 'B' are the given numbers.
Time Limit: 1 sec
Approaches
1. Run a loop from i = 2 to i = min(m, n).
2. Find the remainder for (m / i) and (n / i).
3. If both the remainders are zero, then m and n are not co-prime.
4.If you run through the entire loop without finding an 'i' that divides both m and n, then they are co-prime.
1. Find the GCD of the two numbers and see if it's equal to 1.
2. Here's a property of GCDs that you'll find useful. GCD(a, b) = GCD(b, a%b) where a%b is the remainder left when you divide a by b.