Greatest Common Divisor Loop

Question

I'm doing some self-taught Java, but can't seem to figure out the issue in this loop:

The question was to find the greatest common divisor of two integers n1 and n2 where d is the lesser value. The method is to decrement d until a GCD or it reaches 1...here's where I'm at so far:

    Scanner input = new Scanner(System.in);
    System.out.println("Please enter two integers: ");
    int n1 = input.nextInt();
    int n2 = input.nextInt();

    int d = 0;
    int temp = 0;
    //finds the lowest value
    if(n1 < n2) {
        temp = n1;
        n1 = n2;
        n2 = temp;
    }

    for(d = n1;(n1 % d !=0 && n2 % d != 0);d--)  {

    }

    System.out.println("The GCD of " + n1 + " and " + n2 + " is " + d);

Any pointers?

This isn't your problem but you can start with the smaller of the two, since the GCD will never be greater then the smaller input. — cmd, May 07 '13 at 16:17

score 6 · Accepted Answer · answered May 07 '13 at 16:13

6

The logic in here is wrong:

(n1 % d !=0 && n2 % d != 0)

change to:

(n1 % d !=0 || n2 % d != 0)

Or the code will stop once is saw a divisor of n1 or n2, instead of their GCD, since the loop termination condition should be the negation of what you want to do.

answered May 07 '13 at 16:13

zw324

26,764
16
85
118

Major duh moment! Thanks – mikedugan May 07 '13 at 16:18

score 1 · Answer 2 · answered Oct 20 '13 at 01:51

Iterative

public static long gcd(long a, long b){
   long factor= Math.max(a, b);
   for(long loop= factor;loop > 1;loop--){
      if(a % loop == 0 && b % loop == 0){
         return loop;
      }
   }
   return 1;
}

Iterative Euclid's Algorithm

public static int gcd(int a, int b) //valid for positive integers.
{
    while(b > 0)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

Optimized Iterative

static int gcd(int a,int b)
    {
        int min=a>b?b:a,max=a+b-min, div=min;
        for(int i=1;i<min;div=min/++i)
            if(max%div==0)
                return div;
        return 1;
    }

Recursive

public static long gcd(long a, long b){
   if(a == 0) return b;
   if(b == 0) return a;
   if(a > b) return gcd(b, a % b);
   return gcd(a, b % a);
}

Built-in

import java.math.BigInteger;

public static long gcd(long a, long b){
   return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}

via - http://rosettacode.org/wiki/Greatest_common_divisor

Maybe i got something wrong, but if i use the "optimized iterative" version with the inputs 15 and 35 i get a gcd of 7. Im coding in c if this could be an operator precedence thing? — pluto9800, Sep 17 '21 at 16:48

score 0 · Answer 3 · answered May 07 '13 at 16:19

0

What about doing like this:

for(d = n1; d > 1; d--)  {
    if(n1%d == 0 && n2%d == 0)
        break;
}

answered May 07 '13 at 16:19

sha1

153
7

It will automatically break when it reaches the loop continuation condition – mikedugan May 07 '13 at 16:41
You mean, in `d > 1` part? – sha1 May 07 '13 at 17:18
I tested with some input, but I couldn't see any problem here. – sha1 May 07 '13 at 17:29
I was referring to the original I posted, saying that it would automatically break when a GCD or 1 is reached. Not that yours is wrong, but it adds unnecessary code – mikedugan May 08 '13 at 03:40

score 0 · Answer 4 · answered May 07 '13 at 16:38

0

public static int gcd(int a,int b)

{
    if(a>b)
        if(a%b==0)
            return b;
        else
            return gcd(b,a%b);
    else
        if(b%a==0)
            return a;
        else
            return gcd(a,b%a);
}

This is the best method without looping over all the numbers. Try to understand by yourself as that will help you to develop logic, in case you are not able to understand reply me back, i will explain logic.

answered May 07 '13 at 16:38

Pratul Baheti

3
1
2

The loop did all this in one line essentially :) – mikedugan May 07 '13 at 16:41
When two numbers are very big for e.g. 197853,54689 just imagine the amount of loops you will need, while this will happen in far lesser time. :D – Pratul Baheti May 07 '13 at 16:44

score 0 · Answer 5 · answered Aug 04 '13 at 18:16

The problem can be solved in a different way also. Code below is not of mine but i have understood the logic well. Your logic is good and as suggested by answers it's made flawless too,now.My advice to you is to try writting a function for such calculation. If done so u can do tidious work in a very simple way. Code below is a fine example of usefullness of writting functions.

 public static int gcd(int a,int b){
     if(b==0){
       return a;
     }
      return gcd(b,a%b);        
 }
 public static void main(String args[]){
     Scanner input = new Scanner(System.in);
     System.out.println("Please enter two integers: ");
     int n1 = input.nextInt();
     int n2 = input.nextInt();
     System.out.println("The GCD of " + n1 + " and " + n2 + " is " + gcd(n1,n2));

 }

All the best!

Greatest Common Divisor Loop

5 Answers5