Greatest common divisor
This task requires the finding of the greatest common divisor of two integers.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
ALGOL 68
PROC gcd = (INT a, b) INT: ( IF a = 0 THEN b ELIF b = 0 THEN a ELIF a > b THEN gcd(b, a MOD b) ELSE gcd(a, b MOD a) FI ); main : ( INT a = 33, b = 77; printf(($x"The gcd of"g" and "g" is "gl$,a,b,gcd(a,b))); INT c = 49865, d = 69811; printf(($x"The gcd of"g" and "g" is "gl$,c,d,gcd(c,d))) )
The output is:
The gcd of +33 and +77 is +11 The gcd of +49865 and +69811 is +9973
Forth
: gcd ( a b -- n ) begin dup while tuck mod repeat drop ;
J
x+.y
Java
Iterative
public static long gcd(long a, long b){ long factor= 0; factor= Math.max(a, b); for(long loop= factor;loop > 1;loop--){ if(a % loop == 0 && b % loop == 0){ return loop; } } return 1; }
Recursive
public static long gcd(long a, long b){ if(a == 0) return b; if(b == 0) return a; if(a > b) return gcd(b, a % b); return gcd(a, b % a); }