Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 15 of 15

Thread: Finding the Greatest Common Denomenator

  1. #1
    Member
    Join Date
    Aug 2014
    Posts
    38
    My Mood
    Confused
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default 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?


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,009
    Thanks
    52
    Thanked 2,365 Times in 2,319 Posts

    Default Re: Finding the Greatest Common Denomenator

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

    See the API doc: http://docs.oracle.com/javase/7/docs/api/
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Aug 2014
    Posts
    38
    My Mood
    Confused
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Finding the Greatest Common Denomenator

    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);

  4. #4
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 697 Times in 679 Posts

    Default Re: Finding the Greatest Common Denomenator

    The preferred term is Greatest Common Factor (GCF) (or less precise, Greatest Common Divisor (GCD)).

    I suppose your algorithm will work, but I'm not sure of the purpose of the counter. Store the number that results in a remainder of 0 for both numbers until a larger number is found to replace it.

    There are more efficient ways to find the GCF which you can read about by searching the 'net.

  5. #5
    Member
    Join Date
    Aug 2014
    Posts
    38
    My Mood
    Confused
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Finding the Greatest Common Denomenator

    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.

  6. #6
    Member
    Join Date
    Aug 2014
    Posts
    38
    My Mood
    Confused
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Finding the Greatest Common Denomenator

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

  7. #7
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 697 Times in 679 Posts

    Default Re: Finding the Greatest Common Denomenator

    How are we supposed to help? Post the complete algorithm you've coded, preferably in a runnable example that demonstrates undesired results.

  8. #8
    Member
    Join Date
    Aug 2014
    Posts
    38
    My Mood
    Confused
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Finding the Greatest Common Denomenator

    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.

  9. #9
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 697 Times in 679 Posts

    Default Re: Finding the Greatest Common Denomenator

    Add print statements to the do{} loop to see the results each time through. That may give you some insight into what's happening.

    Hints: Your algorithm doesn't know when to stop, and the logic to assign GCD is wrong.

    Edit: When checking a program, choose some simple functionality that you know should cause a result and test that. For example, build logic that presents a result for the GCF of 1. Though you may not have intended it, your current logic should work for 1, but it doesn't. Why not? Once you've gotten that working, then modify it so that 1 is the default answer, not a calculated answer. For 15 and 25, 2 should not be a GCF, so verify that that 2 is not presented as a result for 15 and 25, etc. Consider testing initially with two simple numbers like 3 and 3 and then increase the difficulty to see how your program responds.

  10. #10
    Member
    Join Date
    Aug 2014
    Posts
    38
    My Mood
    Confused
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Finding the Greatest Common Denomenator

    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'?

  11. #11
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 697 Times in 679 Posts

    Default Re: Finding the Greatest Common Denomenator

    I feel like I'm missing something in that for loop.
    Get in touch with your feelings. They're right.

    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.

    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?

    This illustrates that it's often a good idea to write out what you want your code to do in your native language in code comments and then write code to match the comments. Your sense of what the if() condition should be is stated correctly in English above, but you didn't code it that way.

  12. #12
    Member
    Join Date
    Aug 2014
    Posts
    38
    My Mood
    Confused
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Finding the Greatest Common Denomenator

    Quote Originally Posted by GregBrannon View Post
    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.

    Quote Originally Posted by GregBrannon View Post
    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)?

  13. #13
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 697 Times in 679 Posts

    Default Re: Finding the Greatest Common Denomenator

    This is what it says unless you've changed your code and NOT posted an update:

    if (firstResult == 0 || secResult == 0)

    || != AND

    If you've updated your code, then post the update. It's impossible to help you with code we can't see and talking about old code and new code as though they're the same when they're not is a complete waste of time. I prefer you post the update in a new post so that the evolution of the code is clear and the conversation in between the updates makes sense.

  14. #14
    Member
    Join Date
    Aug 2014
    Posts
    38
    My Mood
    Confused
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Finding the Greatest Common Denomenator

    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.

  15. #15
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 697 Times in 679 Posts

    Default Re: Finding the Greatest Common Denomenator

    Good! Keep pluggin'.

  16. The Following User Says Thank You to GregBrannon For This Useful Post:

    mattig89ch (October 9th, 2014)

Similar Threads

  1. com.Common pacakge
    By talbe in forum What's Wrong With My Code?
    Replies: 5
    Last Post: December 18th, 2012, 10:08 AM
  2. common tasks in java
    By gorgoro in forum Java Theory & Questions
    Replies: 9
    Last Post: October 4th, 2012, 05:26 AM
  3. Recursion, arrays and greatest common divisor
    By GalBenH in forum What's Wrong With My Code?
    Replies: 3
    Last Post: January 14th, 2012, 11:46 PM
  4. Common Java Mistakes
    By helloworld922 in forum Java Code Snippets and Tutorials
    Replies: 13
    Last Post: March 8th, 2011, 12:33 AM