• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

I need help with the following code to find greatest common divisor.

 
Alain Fallada
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, I need help with the following code. It does not work with all cases for example if i enter 84 and 48.

 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What formula are you trying to use to get the GCD? The code isn't right, but I don't know if you've got an incorrect implementation of the right algorithm, or a correct implementation of the wrong algorithm. At the moment you're just taking the modulus of one of the values with respect to the other, which isn't correct.

Take the example you've given: 84 and 48. Your code just calculates 84 % 48, which is 36, which isn't a common divisor of either of them. The easiest approach I know is probably the Euclidean algorithm, which uses modular arithmetic, but needs multiple calculations (so either a loop or a recursive function). The recursive calculation goes something like:

 
Rob Spoor
Sheriff
Pie
Posts: 20611
63
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There's a flaw in there somewhere; the GCD is not 4 but 12. That's because 48 % 36 is not 8 but 12. The flow then becomes this:
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Good point. Thanks!

(Typical mathematician - can cope with the difficult stuff and then makes errors with basic arithmetic )
 
Alain Fallada
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, thank you I understood how to do it.
This is my final version and it works.

 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic