CODEWITHSUNDEEP
javaalgorithm
phantasms
phantasms

Reputation: 29

My Euclid Algorithm is working very slowly

This code compiles fine, but when I run it, it asks for my two numbers as expected and then just sits there and doesn't do anything at all. I've searched the Internet and worked on this all day. I'm finally caving and asking for help.

Is the issue that it's not looping back up automatically? After 10 hours at this, I've found nothing.

import java.util.Scanner;

public class EA
{
    public static void main (String[] args)
    {
        // get first integer from user
        Scanner input = new Scanner(System.in);
        System.out.println("Please enter the larger integer: ");
        int I;
        I = input.nextInt();

        // get second integer from user
        System.out.println("Please enter the smaller integer: ");
        int J;
        J = input.nextInt();

        //resolve the issue of zero
        while(J<1)
        {
            System.out.println("Can not divide by zero!");
            System.out.println("Please enter new smaller integer: ");
            J = input.nextInt();

            //do the calculations
            while(J>0)
            {
                int Remainder;
                Remainder = I % J;

                while(Remainder>0)
                {
                    I = J;
                    J = Remainder;

                    return;

                }
                System.out.println("GCD is" + J);
            }
        }
    }
}

Upvotes: 0

Views: 198

Answers (5)

The_Fresher
The_Fresher

Reputation: 77

Well Euclid's algorithm has a drawback as both the inputs should be non zero to compute the Greatest common divisor . But if you want to find out the GCD when one of the input is a zero ('0') tweak the logic a bit . When one of the input is zero the GCD is 1, and 'a' should be greater than 'b' to compute GCD. Check the snippet below: 

    if (a < b) {
        int temp = a;
        a = b;
        b = temp;
    }
    if (b == 0) {
        System.out.println("1");
    } else {
        while (b != 0) {
            r = a % b;
            a = b;
            b = r;
        }

Upvotes: 0

Luca Mastrostefano
Luca Mastrostefano

Reputation: 3281

There are more than 1 error: the return in the while, the algorithm and the brackets of the first while.

1) When you resolve the issue of zero, the brackets of the while must be closed suddenly after you re-assign the value of the variable J.

while (J < 1) {
    System.out.println("Can not divide by zero!");
    System.out.println("Please enter new smaller integer: ");
    J = input.nextInt();
}

2) The algorithm for computing the gcd is the following:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod t
       a := t
    return a

Here is the correct version of your code:

public static void main(final String[] args) {
    // get first integer from user
    final Scanner input = new Scanner(System.in);
    System.out.println("Please enter the larger integer: ");
    int I;
    I = input.nextInt();

    // get second integer from user
    System.out.println("Please enter the smaller integer: ");
    int J;
    J = input.nextInt();

    // resolve the issue of zero
    while (J < 1) {
        System.out.println("Can not divide by zero!");
        System.out.println("Please enter new smaller integer: ");
        J = input.nextInt();
    }
    // do the calculations
    while (J != 0) {
        int Remainder;
        Remainder = I % J;
        I = J;
        J = Remainder;
    }
    System.out.println("GCD is" + I);

}

Upvotes: 0

Nir Alfasi
Nir Alfasi

Reputation: 53535

SJuan mention that the return breaks the loop, which is true, but even if it's fixed there are a few other issues:

  • The inner while never end (infinite loop)
  • The result will be stored in J - not in I
  • System.out.println("GCD is " + I); Should be printed outside of the outer while!

The "heart" of your program should do this:

    // we get here with valid values stored in I,J
    int Remainder  = I % J;
    //do the calculations
    while(Remainder>0)
    {
        I = J;
        J = Remainder;
        Remainder  = I % J;
    }
    System.out.println("GCD is " + J);

Upvotes: 2

paddy
paddy

Reputation: 63481

Among other things already mentioned, you are confusing while with if. You have put your algorithm logic inside a while loop that only runs if the first input is bad.

// get first integer from user
Scanner input = new Scanner(System.in);
System.out.println("Please enter the larger integer: ");
int I;
I = input.nextInt();

// get second integer from user
System.out.println("Please enter the smaller integer: ");
int J;
J = input.nextInt();

//resolve the issue of zero
while(J<1)
{
    // You never reach here under ordinary conditions
}

Upvotes: 2

SJuan76
SJuan76

Reputation: 24895

The return in the middle of the loop will end the execution.

This one

 while(Remainder>0)
 {
     I = J;
     J = Remainder;

    return; <------- THIS IS THE RETURN THAT BREAKS ALL

 }

so it does not get to the System.out.println.

UPDATE: Also, you do input.nextInt() twice for J. Probably from your description, it keeps waiting for you for entering the third integer.

Upvotes: 0

Related Questions