Algorithm: Euler’s GCD


code:

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:

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:

#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

It would be a great help, if you support by sharing :)
Author: zakilive

Leave a Reply

Your email address will not be published.