Problem: Write a Java program to find if given two numbers are coprime.
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.
- 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.
Note: I have not handled all the scenarios like when both input numbers are same or input numbers are one or negative etc. You can add validation in above program to make it more perfect. I have just shared the logic.
If you have any other logic of solving above problem, please comment. It is always better to know more logic.
If you like my posts, please like, comment, share and subscribe.