Relatively Prime in Java

In this article, you will be very well equipped with a knowledge of a relatively prime number and also Java programs to determine whether a given integer is a relatively prime number or not. Both academics and interviews for Java coding positions regularly question about the reasonably prime number programs.

First of all, lets us recall about the prime number that we have learnt long ago in our school.

Prime Number

A prime number is a number that can be divided only by 1 and by the number itself. let us consider a number 'p'. Divide the number p by all integer q values that are smaller than or equal to the square root of p to determine if a given number is a prime or not. P is a composite number if it can be divided neither by itself nor by one.

Let us understand it with a very simple example.

Consider number 10.

The number 10 can be divisible by 1,2,5,10.

Also consider a number 11.

The number 11 can only be divisible by 1 and the number 11 itself.

Now as we have acquired the general knowledge about the prime numbers, now lets move on to the relatively prime numbers in java.

Relatively Prime Numbers

The numbers that only have the number 1 as their common divisor are referred to as relatively prime numbers. Therefore, 1 is the largest common divisor of both numbers. Coprime numbers are another term for relatively prime numbers.

Let us understand it through a simple example.

Consider numbers 16 and 17

The factors of 16 are (1,2,4,8,16)

The factors of 17 are (1,17)

From the above observation, the numbers 16 and 17 have 1 as their greatest common divisor. Therefore, those two numbers are considered as relatively prime numbers.

Now lets us understand the concept of relatively prime numbers by a program. Go through the program flow to understand it.

File name: CoPrime.java

import java.util.ArrayList;  
import java.util.Collection;  
import java.util.List;  
import java.util.Scanner;  
public class CoPrime   
{  
    /* This is the method for finding and showing the factore of the given two numbers. */  
    static List<Integer> printDiv(int n)  
    {  
        List<Integer> lstDiv= new ArrayList<>();  
        int maxD = (int)Math.sqrt(n);  
        for (int i=1; i<=maxD; i++)  
        {  
            if (n%i==0)  
            {  
                /* Displays only once if the factors are same for both */  
                if (n/i == i)  
                    lstDiv.add(i);  
                  
                // In this else block it will display both the numbers separately  
                else   
                {  
                    lstDiv.add(i);  
                    lstDiv.add(n/i);  
                }  
            }  
        }  
        return lstDiv;  
    }  
      
   
    public static void main(String[] ar)  
    {  
        Scanner sc= new Scanner(System.in);  
        /*Taking the input greater than 1 from the user. */  
        System.out.println("Enter the first number that must be greater than zero:");  
        int num1= sc.nextInt();  
        /* Taking another input from user that shound not match the first number. */  
        System.out.println("Enter the second number that must be greater than zero and should not match the first number:");  
        int num2= sc.nextInt();  
        /* Computing the factors of the first number */  
        System.out.println("Factors of "+num1+" are: ");  
        List<Integer> l1= printDiv(num1);  
        System.out.println(l1);  
        /* Computing the factors of the second number */  
        System.out.println("The factors of "+num2+" are: ");  
        List<Integer> l2= printDiv(num2);  
        System.out.println(l2);  
          
        /* Finding common elements in both the lists */  
        l1.retainAll(l2);  
          
        /* Verify if numbers are relative primes */  
        if(l1.size()==1 && l1.get(0)==1)  
        {  
            System.out.println("The first number "+num1+" and the second number "+num2+" are relatively prime numbers.");  
        }  
        else  
            System.out.println("The first number "+num1+" and the second number "+num2+" are not relatively prime numbers.");  
    }  
      
}  

Output

Enter the first number that must be greater than zero:
50
Enter the second number that must be greater than zero and should not match the first number:
51
Factors of 50 are:
[1, 50, 2, 25, 5, 10]
The factors of 51 are:
[1, 51, 3, 17]
The first number 50 and the second number 51 are relatively prime numbers.

The above is an output when two numbers are relatively prime numbers.

Enter the first number that must be greater than zero:
20
Enter the second number that must be greater than zero and should not match the first number:
22
Factors of 20 are:
[1, 20, 2, 10, 4, 5]
The factors of 22 are:
[1, 22, 2, 11]
The first number 20 and the second number 22 are not relatively prime numbers.

The above is the output when the two numbers are not relatively prime numbers.

Two numbers - num1 and num2 - are provided from the users in the Java code above. The method printDiv() is used to determine the factors of these two numbers, and if none of them has any comparable factors apart from 1, the numbers are considered relatively prime numbers. Else the numbers shall be considered as not relatively prime numbers.