GCD Greatest Common Divisor(Factor)/Highest Common Factor

এখানে লজিকটা হচ্ছে…Here the logic is:
For 12:
1×12=12
2×6=12
3×4=12
So factor of 12=1,2,3,4,6,12
(We don’t need the negative values here)

For 30:
1×30=30
2×15=30
3×10=30
5×6=30
So factor of 30=1,2,3,5,6,10,15,30

Now which is the common factor among 12 and 30
So factor of 12=1,2,3,4,6,12
So factor of 30=1,2,3,5,6,10,15,30

common factor=1,2,3,6
Largest common factor here=6

So now if we divide 12/6 then we get 2
and for 30/6 we get 5

that is all divided perfectly so the logic should be like this

1.Find all the factors of each number
2. Circle the common factors
3. Choose the greatest of those
4. Divide the existing number with greatest common factor thern also get a perfect divide

Here is my code:

#include<stdio.h>
 int main()
{
    int a,b,x,gcd;
    scanf("%d %d",&a,&b);

    if(a<b)//it is not possible for gcd to be greater than the lowest value
    {
        x=a;
    }
    else
    {
        x=b;
    }
    for( ;x>=1;x--){ //here i haven't initialized the value of x as x is first at outside
        if(a%x==0 && b%x==0){
            gcd=x;
            break; //here i have used break as if it is not here then when the division will happen it will run the loop till 1 so answer will be always 1
        }
    }

printf("GCD is %d\n",gcd);

    return 0;
}

gcd

Here is a link that described many thinks about this clearly: http://www.mathsisfun.com/greatest-common-factor.html

 

Another method can also apply here:
link for understanding the modarithmetic euclidean algorithmhttps://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

Code:

#include<stdio.h>

int main()
{

    int a,b,t,x,gcd;
    scanf("%d %d",&a,&b);
    if(a==0)
        gcd=a;
    else if(b==0)
        gcd=b;
    else
    {
        while(b!=0)
        {

            t=b;
            b=a%b;
            a=t;
        }
        gcd=a;
    }
    printf("GCD is %d\n",gcd);

    return 0;
}

 

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

Leave a Reply

Your email address will not be published. Required fields are marked *