https://www.youtube.com/watch?v=WAyPIMme3Yw&index=8&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int euclid_gcd(int a,int b) { int dividend,divisor,remainder; dividend = a>=b?a:b; divisor= a<=b?a:b; while(divisor!=0) { remainder=dividend%divisor; dividend=divisor; divisor=remainder; } return dividend; } |
more optimized:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int euclid_gcd(int a,int b) { int dividend,divisor,remainder; dividend = a; divisor= b; while(divisor!=0) { remainder=dividend%divisor; dividend=divisor; divisor=remainder; } return dividend; } |
Recursive:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include<bits/stdc++.h> int euclid_gcd_recursive(int a,int b) { return b==0?a:euclid_gcd_recursive(b,a%b); } int main() { int d,x,z; printf("Scanf a and b:"); scanf("%d %d",&x,&z); d=euclid_gcd_recursive(x,z); printf("GCD= %d",d); return 0; } |
http://www.progkriya.org/gyan/basic-number-theory.html#section3