Check If Given Numbers Are Coprime

Easy

0/40

Average time to solve is 28m

Contributed by

10 upvotes

Problem statement

You have been given two numbers 'a' and 'b'. Write a function that checks if the given numbers are co-prime.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
5 10

Sample Output 1:

false

Explanation For Sample Output 1:

Since 5  and 10 both are divisible by 5, they are not co-prime. 
Hence the output is false.

Sample Input 2:

2
7 11
11 13

Sample Output 2:

true
true

Hint 1

Hint 2

Try to divide both the numbers with all numbers from 2 to (min(m,n) - 1)? If the same number divides both the numbers, then what can you say about the 2 numbers?

Approaches (2)

Approach 1

Approach 2

Divide And Find Remainder

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.

Time Complexity

O(min(m, n)), where m and n are the two input integers.

Since we are running a loop till min(m,n), the time complexity will be O(min(m,n)).

Space Complexity

O(1).

Constant space is used.

(100% EXP penalty)

Check If Given Numbers Are Coprime

Console