Determining common divisors of two numbers

Question

Is there a better algorithm for finding the common divisors of two numbers? Can this code be shortened?

import java.util.*;

public class Testing1 {
public static void main (String args[]){
    Scanner x=new Scanner(System.in);
    System.out.print("Enter the 1st number(larger number) :  ");
    int y=x.nextInt();
    System.out.print("Enter the 2nd number : ");
    int z=x.nextInt();

    int ar1[]=new int[y];
    int ar2[]=new int[z];

    for( int i=1;i<y;i++){ //puts the divisors of the larger number to an array ar1[]
         int l=y%i;
         if(l==0)
           ar1[i]=i;}

    for( int i=1;i<z;i++){//puts the divisors of the other number to an array ar2[]
        int l=z%i;
        if(l==0)
          ar2[i]=i;}System.out.print("Common divisors of "+y+", "+z+" = ");

    for(int i=1;i<=ar2.length-1;i++){ //printing the common elements of both arrays.
     if((ar1[i]==ar2[i])&&ar2[i]!=0)
        System.out.print(i+" ");
}}}

Answer 1

There are few improvements you can do in your code:

• First choose better variable names. I would name the Scanner type variable as scanner rather than x. Really, x, y, z are the worst variable name, which doesn't give any idea as to what they denote.

• Secondly, I won't force user to pass larger number first, and then smaller number. I would take the burden of finding that out myself.

• There is no need of storing all the divisors of both the numbers in two different arrays. Suppose you have to find common divisor of 2 and 2132340. Will you store all the divisors of 2132340, or simply check that the common divisor cannot be greater than the divisor of 2, and use that fact?

• Another fact is, all the divisors of num1 will be less than or equal to num1 / 2. Now, if num1 < num2, then the common divisors all must be < num1 / 2. So, iterate the loop till min / 2.

• Of course, you can move the code that finds the common divisor in a different method, and store them in a List<Integer>.

• Lastly, it might be possible that the smaller number itself is a divisor of larger number. So, you need to store that too.

Here's the modified code which looks a bit cleaner:

public static void main (String args[]){
    Scanner scanner = new Scanner(System.in);

    System.out.print("Enter the 1st number :  ");
    int num1 = scanner.nextInt();
    System.out.print("Enter the 2nd number : ");
    int num2 = scanner.nextInt();

    List<Integer> commonDivisor = getCommonDivisor(num1, num2);
    System.out.println(commonDivisor);
}

public static List<Integer> getCommonDivisor(int num1, int num2) {

    List<Integer> list = new ArrayList<Integer>();

    int min = minimum(num1, num2);

    for(int i = 1; i <= min / 2; i++) { 
        if (num1 % i == 0 && num2 % i == 0) {
            list.add(i);
        }
    }

    if (num1 % min == 0 && num2 % min == 0) {
        list.add(min);
    }

    return list;
}

public static int minimum(int num1, int num2) {
    return num1 <= num2 ? num1 : num2;
}

Answer 2

1. This might have been mentioned before but here it is anyway: You should format your code. Badly formatted code is hard to read - it might be the most efficient code in the world but it's still hard to read and maintain and easy to miss bugs or easy to add bugs.

   It also shows a lack of attention to detail and programming is all about attention to detail. It basically demonstrates that not much care has been put into. Whenever you write some code imagine you'd have to show it as an example of your work for your next job interview.

2. You should name your classes and variables better. While i is acceptable for a loop variable l, x, y, and z should be renamed to reflect what their meaning is. It is especially confusing since x suggests to have a similar meaning to y and z while it actually is completely different (it represents a form of input rather than a number).

3. You should use an ArrayList rather than a fixed size array to store the divisors. If someone inputs 2147483647 then your program would try to allocate an array with 2,147,483,647 elements - approx. 8GB of memory even though it's a prime number.

   If you change this then your check for the common divisors need to check the common subset s of both lists instead.

4. Your two for loops do the exact same thing except on different inputs. They should be refactored into one common method which performs the calculation and gets the number to check as input.

5. Your algorithm is buggy. For example if you check 2 and 4 you will not find 2 as a common divisor.

Answer 3

You should factor out your code for finding one number's divisors into an own function like:

List<Integer> getDivisors(Integer number) {
    List<Integer> divisors = new List<Integer>();
    for(int currentDivisor = 1; currentDivisor <= number; currentDivisor++)
        if(number % currentDivisor == 0)
            divisors.add(currendDivisor);
    return divisors;
}

Instead of just using this function in the code you should also revise the algorithm a bit. As indicated by jpreen in a comment you should use Euclid's algorithm for finding the gcd of two numbers.

Once you have the gcd you can derive all further common divisors from it because all common divisors of two numbers are divisors of the gcd of the two numbers.

Thus your code would become:

List<Integer> getCommonDivisors(Integer x, Integer y) {
    return getDivisors(gcd(x, y));
}

The advantages of this approach are:

• the gcd does not depend on the order of the arguments
• the gcd is always at most the minimum of the arguments (which makes it effiecient in the case 2, 2132340 mentioned in another answer)
• the code is short and concise (however it should be documented why the trick with the gcd works)