Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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+" ");
}}}
share|improve this question
4  
You have already accepted an answer, and I don't code in java, but as a mathematician, I would like to point out that there is a very nice recursive algorithm which is much shorter; the Euclidean Algorithm: math.rutgers.edu/~greenfie/gs2004/euclid.html –  jpreen Dec 8 '13 at 14:54
    
(the common divisors are necessarily the divisors of the greatest common divisor) –  jpreen Dec 9 '13 at 18:37

3 Answers 3

up vote 6 down vote accepted

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;
}
share|improve this answer
    
Thank you for your advice.I will go through this and try to improve myself.:) –  Razor1692 Dec 8 '13 at 9:12
    
I get a run time error in this code saying "the method minimum(int, int) is undefined for the type ComDivi" . My class name was ComDivi. How can i solve this problem? –  Razor1692 Dec 8 '13 at 9:35
    
@Razor1692 You forgot to add the minimum method. Check the complete code in my answer. –  user3011937 Dec 8 '13 at 10:09
  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.

share|improve this answer
    
Thank you for your advice.I will learn from this.:) –  Razor1692 Dec 8 '13 at 9:11

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)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.