Thread: Finding the Greatest Common Denomenator

Hidy ho all,

I just got an assignment where I have to find the Greatest Common denominator of 2 numbers that a user inputs.

My first idea on how to do this is to loop through both numbers to find which numbers between 0 and the inputed number, then store those numbers in a dynamic array, before finally comparing the two arrays to find which ones are equal.

Since I have no idea how many denomenators are in each array, I need to use a dynamic array. Now I'm coming to java from C++ so I know how to use vectors. My question is, are vectors able to be used in java? If so, where can I find more info on them?

The ArrayList class is commonly used to store varying amounts of data.

See the API doc: http://docs.oracle.com/javase/7/docs/api/

Thanks for that link. I think I may have a way to do it w/out using arrays. Would someone mind checking my logic to see how right or wrong I am?

First the user inputs 2 numbers.

Next I check which of the 2 numbers is the biggest using an if else statement. If the first number is the biggest it gets stored in biggest variable and the second number is stored in a smaller variable, else the second number is stored in the biggest variable and the first is stored in the smaller variable.

Then I run the numbers through a loop with a counter in it. The first and second numbers are put through the % operator (firstNumber % counter, secondNumber % counter) so I can find where their remainders are 0. If the remainder is 0 on both of them, I then store the counter in a GCD variable and increment the counter by 1 (counter ++). This is done so long as the counter is less then the smaller number. Remember, I need to find the greatest common denominator of both numbers.

Finally, I output the GCD variable.

heres the code:

        if (firstInput > secInput)
        {
            largest = firstInput;
            smallest = secInput;
        }
        else
        {
            largest = secInput;
            smallest = firstInput;
        }
 
        do{
 
 
            firstResult = firstInput % counter;
            secResult = secInput % counter;
 
            if (firstResult == 0 || secResult == 0)
            {
                GCD = counter;
            }
 
        counter ++;
        }
        while (counter < smallest);
 
        System.out.println("The Greatest Common Denominator is: " + GCD);

Right-o. I'm running the math through a do-while loop that terminates when the counter reaches the size of the smallest variable.

The counter both controls the loop and provides something to get the remainder from.

I entered 25 and 30. It spat back 15 as the gcd. So something is wrong.

Ok, I still haven't been able to find where my problem is. Does anyone know where my logic is going bad?

I did acutally, but I'll post it again.

int firstInput = Integer.parseInt(JOptionPane.showInputDialog("Enter First number"));
        int secInput = Integer.parseInt(JOptionPane.showInputDialog("Enter Second number"));
        int GCD = 0, largest =0, firstResult =0, counter = 1, smallest = 0, secResult = 0;
 
        if (firstInput > secInput)
        {
            largest = firstInput;
            smallest = secInput;
        }
        else
        {
            largest = secInput;
            smallest = firstInput;
        }
 
        do{
 
 
            firstResult = firstInput % counter;
            secResult = secInput % counter;
 
            if (firstResult == 0 || secResult == 0)
            {
                GCD = counter;
            }
 
        counter ++;
        }
        while (counter < smallest);
 
        System.out.println("The Greatest Common Denominator is: " + GCD);

I put 25 and 30 into it. Now done by hand the GCD is 5, with the program I get 15 as a result. So I know thats not right. Trouble is, I don't know where I'm going wrong to make it right.

Edit: just in case it comes into question, I do have import javax.swing.*; at the very tippy top. It compiles fine, it gives no errors when it runs. The only problem seems to be the math.

ok, I'm with you so far. I think.

its supposed to stop when the counter reaches the smallest number. And only assign anything to the GDC variable if the firstResult and secResult are both 0.

The print statement in the for loop (when the GCD is assigned to the counter) produced 1, 2, 3, 5, 6, 10, 15. I feel like I'm missing something in that for loop. Some other conditional statement that would say dont assign counter to gcd unless it produces whole numbers. Because when you do the math by hand, some of the results are decimals. Is there a way to say something like 'if first result and second result are 0 and whole numbers'?

Originally Posted by GregBrannon

As for your "whole numbers" comment, when would the % operator result in other than a whole number? I'm not sure that thinking is relevant here.

At this point, I'm getting decimals in my returns. no idea why. For example, if you divide 25 by 10 the result is 2.5. But when its saying that 25 % 10 = 0, so its storing 10 in GCD.

Originally Posted by GregBrannon

However, your question, "Is there a way to say something like 'if first result and second result . . ." IS relevant. What is the if() statement condition currently? Does it agree with your question?

At the moment its saying that if the firstNumber % counter = 0 AND secNumber % counter = 0 then store counter in the GCD variable. My understanding of these math equations is that firstNumber % counter finds the remainder. Is it possible for 25 % 10 to equal 0? Shouldn't it be 5 (20/10 = 2 with remainder of 5)?

oooooohhhhhhh, thats where the problem is then. I thought that || meant and. um....what does it mean?

Edit: just updated the code, 25 and 30 now produce a result of 5! Woo! Thanks for your help my good man!

Now to test some other numbers to see if there are other problems.