Register to reply 
Gcd methodby JaysFan31
Tags: method 
Share this thread: 
#1
May2307, 10:56 PM

P: n/a

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:
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 


#2
May2407, 02:38 AM

Sci Advisor
HW Helper
P: 2,586

If you have a for loop, I don't think you want to use a variable with a larger scope as the counter variable. And you also don't need to copy the code for the case c > a. You can say "if a % c == 0  c % a = 0 {return min(a,c);}" and make the for loop only run up to min(a,c). This isn't too creative though, as you can guess. But other than your straightforward approach above and the Euclidean Algorithm, I can't think of any other ways to find the gcd.



#3
May2407, 05:43 AM

Engineering
Sci Advisor
HW Helper
Thanks
P: 6,959

The way you used a local variable "int gcd" inside the function with the same name "public static int gcd(...)" is confusing (though not actually wrong).
In Java you can just say return c; instead of gcd = c; return gcd; I wonder if you found some Fortran code and tried to translate it into Java. In Fortran you would write something like function gcd(....) integer gcd ... gcd = c return But that (slightly strange) syntax is specific to Fortran, Java and C are different. The efficient way to find the GCD is Euclid's algorithm (look it up on Google). You can either write the code using a loop, or use a recursive function. (If you haven't gone recursion yet, come back to this later.) 


#4
May2407, 12:57 PM

P: n/a

Gcd method
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.



#5
May2407, 05:45 PM

Engineering
Sci Advisor
HW Helper
Thanks
P: 6,959

You have got confused between "&&" to "" which is a common mistake. Often in English you say "and" when you really mean "or", and vice versa.
Actually, the "do {...} while(...)" statement with a complicated "while(...)" condition is often hard to understand, and it is quite a rare statement in most Java programs. A loop which tests at the top, "while(...) { ... }" is much more common. If you use that form of loop, then "&&" is the correct operator and the statement means the same read "in English" and "in Java". There is another advantage of testing at the start of the loop  it gives you the possibility of doing nothing, if the condition is true before you get to the loop. That is often useful. It's certainly useful calculating the gcd, because it handles all your special cases like a = b, a > b and a & b = 0, etc. I came up with this version, which handles all the cases the same way: public static int gcd(int a, int b) { int count = a; if (b < a) { count = b; } while (a % count != 0 && b % count != 0) { count = count  1; } return count; } A recursive function using Euclid's algorithm is even shorter: public static int gcd(int a, int b) { if (a % b == 0) return b; else return gcd(b, a % b); } 


Register to reply 
Related Discussions  
Volume, washer method and shell method  Calculus  5  
Shell method versus disk method  Calculus & Beyond Homework  1  
Help needed fast :S Characteristics of the power method and the inverse power method  Calculus & Beyond Homework  1  
Work energy method and impulse momentum method  Classical Physics  1  
Washer method and disc method for finding volumes of graphs  Calculus  5 