Problem: Write a Java program to find if given two numbers are coprime.
Solution:
Definition of coprime:
As per Wikipedia,
- In number theory, two integers a and b are said to be relatively prime, mutually prime, or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1. Consequently, any prime number that divides one does not divide the other. This is equivalent to their greatest common divisor being 1.
- As specific examples, 14 and 15 are coprime, being commonly divisible only by 1, while 14 and 21 are not coprime, because they are both divisible by 7.
- Read more about coprime numbers here.
Logic:
- First we need to find divisors of input numbers. Finding divisors of a number, we can learn in previous post.
- We will store all divisors in a collection class separately.
- We will find common elements from both collections.
- If common element is found as “1”, we will call given numbers as coprime.
Java code:
Output: