GCD Of Two Numbers

What is Greatest Common Factor? GCD of two numbers is the largest number that divides both of them.

Approach-1

Brute Force

Finding all the prime factors of both the numbers, then finding the product of the intersection.

Finding the largest number that divides both the numbers.

What is it that we do for the same?

• Find out the smaller of the two numbers
  • Why?
  • Example-4,6.
    • Just no point in calculating all the factors of 6 when the largest prime factor will be less than 4
• Run a loop from 1 to the smaller number
• Maintain a variable to keep the answer
• If a number divides both the numbers we simply update the variable

Follow the small process and end up with the largest prime factor of both the numbers!

Still, clueless? Look into the code!

Java Code for GCD Of Two Numbers

import java.util.*;
public class GCD
{
  public static int find_fac(int num1,int num2)
  {
    int ans=1;
    int num=0;
    if(num1>num2)
      num=num2;
    else
      num=num1;
    for(int i=num;i>0;i--)
    {
      if(num1%i==0 && num2%i==0)
      {ans=i;break;}
    }
    return ans;
  }
  public static void main(String args[])
  {
    int gcd=find_fac(12,28);
    System.out.println(gcd);
  }
}

C++ Code for GCD Of Two Numbers

#include<iostream>
using namespace std;
int find_fac(int num1,int num2)
{
  int ans=1; 
  int num=0; 
  if(num1>num2) 
    num=num2; 
  else 
    num=num1; 
  for(int i=num;i>0;i--) 
  { 
    if(num1%i==0 && num2%i==0) 
      {ans=i;break;} 
  } 
  return ans;
}
int main()
{
  int gcd=find_fac(12,28);
  cout<<gcd;
}

4

Complexity Analysis for GCD Of Two Numbers

Time complexity=O(n)

Approach-2

Using the Euclidian Algorithm for GCD

By the Algorithm Principle: HCF does not change on subtracting a larger number from the smaller one.

We know that Repeated Subtraction=Division

Three golden rules one must follow for being smart with the same problem.

Fit them into your head and understand them to the core!

• GCD(a,b)=GCD(b,a) if b>a
• GCD(a,b)=GCD(a,a%b)
• GCD(a,0)=a

If this is too much for you to take in one go do not worry I have a small flowchart for you.

The example in the flowchart-(10,14)

• We find GCD(14,10) as 14>10
  • GCD(14,10)=GCD(14%10,10)
• Work on to calculate the GCD of (4,10)
• HCF of (10,4) will be calculated as 10>4
  • HCF(10,4)=GCD(10%4,4)=GCD(2,4)
• Find the GCD(4,2) as 4>2
  • HCF(4,2)=GCD(4%2,2)=GCD(2,2)
• GCD(2,2)=HCF(0,2)
• Just as we hit 0.Voila we have our answer! 2

Java program for GCD Of Two Numbers

import java.util.*;
public class GCD
{
  public static int find_fac(int num1,int num2)
  {
    if(num2==0)
      return num1;
    if(num1>num2)
      return find_fac(num1%num2,num2);
    else
      return find_fac(num2,num1);
  }
  public static void main(String args[])
  {
    int gcd=find_fac(12,24);
    System.out.println(gcd);
  }
}

C++ Code for GCD Of Two Numbers

#include<iostream>
using namespace std;
int find_fac(int num1,int num2)
{
  if(num2==0)
      return num1;
  if(num1>num2)
      return find_fac(num1%num2,num2);
  else
      return find_fac(num2,num1);
}
int main()
{
  int gcd=find_fac(12,24);
  cout<<gcd;
}

12

Complexity Analysis for GCD Of Two Numbers

Time complexity = O(log(n))

Where n is the minimum of both the numbers

These were the ways of finding the HCF of numbers!

How about we flex the skills on a problem and learn more complex stuff?

Sieve of Eratosthenes!

Sieve of Eratosthenes