# Finding GCD of two numbers

What is Greatest Common Divisor (GCD)?

• Greatest common divisor is also known by the name HCF (Highest Common Factor).
• It is the largest positive integer that divides each of the integers.
• For example, the HCF of 6 and 12 is 6.
Also, the HCF of 8 and 12 is 4.
The HCF of 10 and 30 is 10.
HCF of 12 and 76 is 4.

MATLAB CODE

```x1=input('Enter number 1 :');
x2=input('Enter number 2 :');
a=max(x1,x2);
for i=1:a
if mod(x1,i)==0 && mod(x2,i)==0
GCD=i;
end
end
fprintf('HCF of %d and %d is %d',x1,x2,GCD)
fprintf('\n')

```

# Algorithm

• The HCF of two or more integers is the largest positive integer that divides each of the integers.
• Two numbers are then asked to be entered by the user. Then these two numbers are stored in two variables. Let the two variables be x1 and x2. Also, we keep a variable ‘GCD’.
• A for loop is used where a variable ‘i’ tends from 0 to max(x1,x2).
• Inside for loop the numbers x1 and x2 are then divided by ‘i’ in each loop. Whenever x1 and x2 are exactly divisible by ‘i’ then the value of gcd is set to ‘i’.
• After the for loop has finished being executed, the gcd will have the HCF of two numbers.

# OUTPUT

The following are the output for various numbers inputted

• 6 and 12
• 8 and 12
• 10 and 30
• 12 and 76

##### SAURAB S

I am currently pursuing my btech in Electronics and communication engineering from Amrita Vishwa Vidyapeetham. My areas of interest are signal processing, Communication systems, Control system.

### Recommended Posts

##### Test Post

17 Feb 2018 - Tutorial

##### Counters using conditionally executed subsystems | Simulink Tutorial

16 Feb 2018 - Simulink, Tutorial

##### Regulating drum boiler pressure

16 Feb 2018 - Simulink, Tutorial