Programming Help

Web Development



What's Here?

  • Members: 149,523
  • Replies: 506,638
  • Topics: 79,834
  • Snippets: 2,666
  • Tutorials: 706
  • Total Online: 1,423
  • Members: 68
  • Guests: 1,355

Welcome to Dream.In.Code
Become a Java Expert!

Join 149,523 Java Programmers for FREE! Get instant access to thousands of Java experts, tutorials, code snippets, and more! There are 1,423 people online right now. Registration is fast and FREE... Join Now!




gcd method

 
 Reply to this topicStart new topic

gcd method
PvtBillPilgrim
23 May, 2007 - 07:54 PM
Post #1

New D.I.C Head
*

Joined: 7 May, 2007
Posts: 21


My Contributions
I am a beginner programmer in Java. Just started learning the past few weeks.

I'm taking a class and need to create a method that finds the greatest common divisor of two integers. I can assume that both are positive, but I cannot use the Euclidean Algorithm.

I'm sort of lost, but I think I'm on the right track, although this may look confusing:
CODE

public static int gcd(int a, int c)
{
int gcd;
int attempt;
if (a > c)
{
if (a % c == 0)
{
gcd = c;
return gcd;
}
else
{
for (attempt = c; attempt = 1; attempt--)
do
{
if (c % attempt == 0 && a % attempt == 0)
{
gcd = attempt;
return attempt;
}
}
while (c % attempt != 0 || a % attempt == 0);
}
}

And then I basically copied the code with an else statement if c > a.

I'm sure there are a lot of mistakes. Could someone just point them out and offer a simpler way of doing it (possibly without using the Euclidean Algorithm)?

Thanks.
Michael

This post has been edited by PvtBillPilgrim: 23 May, 2007 - 07:55 PM
User is offlineProfile CardPM
+Quote Post

Mila
RE: Gcd Method
23 May, 2007 - 08:54 PM
Post #2

D.I.C Head
Group Icon

Joined: 28 Oct, 2006
Posts: 94


Dream Kudos: 25
My Contributions
When I learned recursion I had to write a gcd method. It ran something like this:
CODE

int gcd(int a, int b)
{
    if (b > a)
    {
        int temp = b;
        b = a;
        a = temp;
    }

    int remainder = a % b;

    if (remainder == 0)
        return b;
    else
        return gcd(b, r);
}


This was my algorithm:

1. make both numbers positive
2. if a < b, swap them, so that a is >= b
3. if b = 0, a is the gcd
4. if b != 0, remainder = a % b
5. repeat, using b as the new a and remainder as b.
User is offlineProfile CardPM
+Quote Post

PvtBillPilgrim
RE: Gcd Method
24 May, 2007 - 05:33 AM
Post #3

New D.I.C Head
*

Joined: 7 May, 2007
Posts: 21


My Contributions
See I believe that's using the Euclidean Algorithm, which I cannot use.

I think my code above is correct for the most part. It just will not compile. Any ideas why it's wrong?
User is offlineProfile CardPM
+Quote Post

PennyBoki
RE: Gcd Method
24 May, 2007 - 06:44 AM
Post #4

system("revolution");
Group Icon

Joined: 11 Dec, 2006
Posts: 2,010



Thanked: 7 times
Dream Kudos: 500
Expert In: Java,C++,C

My Contributions
Hi, maybe if you post the rest of the code of your program I could be more precise, anyways the only thing that doesn't look right to me is
QUOTE
while (c % attempt != 0 || a % attempt == 0);
}


You have a while loop that does nothing or...

This post has been edited by PennyBoki: 24 May, 2007 - 06:45 AM
User is offlineProfile CardPM
+Quote Post

PvtBillPilgrim
RE: Gcd Method
24 May, 2007 - 09:51 AM
Post #5

New D.I.C Head
*

Joined: 7 May, 2007
Posts: 21


My Contributions
OK. I think this is a lot better. It compiles and makes sense to me at least. However, it doesn't work properly for more difficult integers like 20, 30. Can anyone spot the problem (as I said nothing wrong with compiling, just doesn't work logically). As I said before, I can't use the Euclidean Algorithm, so I basically had to write the simplest program to find gcd.

CODE

public static int gcd(int a, int b)
{
int gcd;
if (a > b && a % b == 0)
{
gcd = b;
return gcd;
}
else if (b > a && b % a == 0)
{
gcd = a;
return gcd;
}
else if (a > b && a % b != 0)
{
int count = b;
do
{
count = count - 1;
}
while (b % count != 0 && a % count != 0);
gcd = count;
return gcd;
}
else if (b > a && b % a != 0)
{
int count = a;
do
{
count = count - 1;
}
while (b % count != 0 && a % count != 0);
gcd = count;
return gcd;
}
else
{
gcd = a;
return gcd;
}
}
User is offlineProfile CardPM
+Quote Post

Mila
RE: Gcd Method
24 May, 2007 - 12:19 PM
Post #6

D.I.C Head
Group Icon

Joined: 28 Oct, 2006
Posts: 94


Dream Kudos: 25
My Contributions
OK. Well, an alternative is finding the least common multiple. Because gcd(a,b) = (a*b) / lcm(a,b).

Finding the least common multiple is easy:
CODE

public int lcm(int a, int b)
    {
        if (a == 0 ||  b == 0)
            return 0;
        
        int index = 1;
        int test = a*index;
        
        while (test <= a*b)
        {
            if (test % b == 0)
                return test;
            
            index++;
            test = a * index;
        }
        
        return a*b;
    }


Basically it just takes each multiple of a and then tries to divide it by b. If it divides cleanly, it's the LCM.

Then have a GCD method that looks like:
CODE

public int gcd(int a, int b)
    {
        return ((a*b) / lcm(a,b));
    }


The only problem you might have would be if lcm(a,b) == 0, but you can trap for that easily.

Cheers.
Mila
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic
Time is now: 1/7/09 08:37PM
Invision Power Board v2.1.7 © 2009  IPS, Inc.
Licensed to: MediaGroup1

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter

Live Java Help!

Java Tutorials

Reference Sheets

Java Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month