C Program To Find GCD & Common Factors of Two Numbers (Euclidean Algorithms)

C Program To Find GCD & Common Factors of Two Numbers (Euclidean Algorithms)

Question

Write a program to find common factors of two numbers using Euclidean algorithm. First of all find GCD (Greatest Common Divisor) of two numbers using this algorithm then find the common factor of GCD.

Methods to Find GCD 

Method I : Program to find GCD of two numbers

Method II : Basic Euclidean Algorithm for GCD

The algorithm is based on below facts.

  • If we subtract smaller number from larger (we reduce larger number), GCD doesn’t change. So if we keep subtracting repeatedly the larger of two, we end up with GCD.
  • Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.

An efficient solution is to use Euclidean algorithm which is the almost used for this purpose.

Logic

The Euclidean Algorithm will find the greatest common divisor. It is based on the fact that gcd(a,b)gcd(a,anb) , so you start by taking the larger modulo the smaller and repeat until you get to 0. For  example

So the greatest common divisor is 2. The common factors will be all the factors of the gcd, so if the it had been 12 the common factors would be 1,2,3,4,6,12. This lets you only factor the that, not the numbers themselves.

Sample Test Cases

Procedure

  • First of all get the two numbers from the user.
  • Find the greatest common factor using gcd().
  • Find the common factors of  gcd and printing it consequently.
  • As a result it is equivalent to the numbers we given.
  • Finally make count of Common factors and  print that count.

Program

#include<stdio.h>
int gcd(int a,int b)
{
    if(b==0)
        return a;
    gcd(b,a%b);
}
int main ()
{
    int a,b,i,cnt=0;
    printf("First Number =");
    scanf("%d",&a);
    printf("Second Number =");
    scanf("%d",&b);
    printf("\nCommon Factors\n");
    for(i=1;i<=gcd(a,b);i++)
        if(gcd(a,b)%i==0)
        {
            printf("%d  ",i);  //printing common factors
            cnt++;
        }
    printf("\nTotal Common Factors =%d\n",cnt);
    printf("GCD is %d\n",gcd(a,b));
   return 0;
}

 

Hari Prasath R

You know who I am :)