## 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 solutionis 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,a−nb) *, 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; }