Pseudocode to Find GCD of Two Numbers

In this program, we’ll learn to find Greatest Common Divisor (GCD) of two numbers in Algortihm.

Pseudocode:


BEGIN
 
NUMBER n1 , n2 , gcd = 1, i
 
OUTPUT "Enter first Number:"
INPUT n1

OUTPUT "Enter second Number:"
INPUT n2
 
 FOR  i = 1; i <= n1 && i <= n2; ++i THEN
    
	IF n1 % i == 0 && n2 % i == 0 THEN
		gcd = i
        END IF
END FOR

OUTPUT " G.C.D of "+n1+"and "+n1+" is "+ gcd
 
END

BEGIN

NUMBER n1 , n2 , gcd = 1, i

OUTPUT "Enter first Number:"

INPUT n1

OUTPUT "Enter second Number:"

INPUT n2

FOR i = 1; i <= n1 && i <= n2; ++i THEN

IF n1 % i == 0 && n2 % i == 0 THEN

gcd = i

END IF

END FOR

OUTPUT " G.C.D of "+n1+"and "+n1+" is "+ gcd

END

This is a pseudocode for finding the greatest common divisor (GCD) of two numbers n1 and n2. The GCD is the largest positive integer that divides both n1 and n2 without a remainder.

Here is a detailed explanation of the code:

The code declares three variables: n1, n2, and gcd. n1 and n2 will be used to store the two input numbers, and gcd will be used to store the greatest common divisor.
The code prompts the user to enter the first number and stores it in n1.
The code prompts the user to enter the second number and stores it in n2.
The code starts a loop that iterates from 1 to the minimum of n1 and n2 (FOR i = 1; i <= n1 && i <= n2; ++i THEN).
Inside the loop, the code checks if i divides both n1 and n2 without a remainder (IF n1 % i == 0 && n2 % i == 0 THEN). If this condition is true, it updates the value of gcd to i.
After the loop ends, the code prints the GCD of n1 and n2 to the console.

This pseudocode uses a simple and efficient method for finding the GCD of two numbers, known as the “iterative” method. It starts from the smallest number and iteratively checks if each number from 1 up to the smallest number divides both numbers without a remainder. The first number that does is the GCD.

Flowchart:

Java Code: Java Program to find gcd of two numbers using for loop


   public static void main(String[] args) {
       
        Scanner scanner = new Scanner(System.in);  // Create a Scanner object
        System.out.print("Enter a Number 1:");
        int n1 = scanner.nextInt();
        
        System.out.print("Enter a Number 2:");
        int n2 = scanner.nextInt();
        
        int  gcd = 1;
        for(int i = 1; i <= n1 && i <= n2; ++i)
        {
            // Checks if i is factor of both integers
            if(n1 % i==0 && n2 % i==0)
                gcd = i;
        }
        System.out.printf("G.C.D of %d and %d is %d \n", n1, n2, gcd);
    }

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in); // Create a Scanner object

System.out.print("Enter a Number 1:");

int n1 = scanner.nextInt();

System.out.print("Enter a Number 2:");

int n2 = scanner.nextInt();

int gcd = 1;

for(int i = 1; i <= n1 && i <= n2; ++i)

{

// Checks if i is factor of both integers

if(n1 % i==0 && n2 % i==0)

gcd = i;

}

System.out.printf("G.C.D of %d and %d is %d \n", n1, n2, gcd);

}

Python Code: Write a program to Find GCD of Two Numbers in Python


# take input from the user
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
 

# choose the smaller number
if num1 > num2:
    smaller = num2
else:
    smaller = num1
for i in range(1, smaller+1):
    if((num1 % i == 0) and (num2 % i == 0)):
        hcf = i

print("The H.C.F. of", num1,"and", num2,"is", hcf)

# take input from the user

num1 = int(input("Enter first number: "))

num2 = int(input("Enter second number: "))

# choose the smaller number

if num1 > num2:

smaller = num2

else:

smaller = num1

for i in range(1, smaller+1):

if((num1 % i == 0) and (num2 % i == 0)):

hcf = i

print("The H.C.F. of", num1,"and", num2,"is", hcf)

JavaScript Code: Write a program to Find GCD of Two Numbers in JavaScript


<body>
    <input type="text" id="b1" placeholder="Enter first number">
<input type="text" id="b2" placeholder="Enter second number">
<input type="button" value="Calculate" id="btnCalc">
 
<div id="result" style="width:250px; border: 1px solid #ddd;position: absolute;top:50px;left:50;padding:20px">
 
</div>
 
<script>
 
function area(){
    var n1=document.getElementById("b1").value;
    var n2=document.getElementById("b2").value;
    var result=document.getElementById("result");
 
    n1=Number(n1);
    n2=Number(n1);
 
    let  gcd = 1;
    for(let i = 1; i <= n1 && i <= n2; ++i)
    {
        // Checks if i is factor of both integers
        if(n1 % i==0 && n2 % i==0)
            gcd = i;
    }
    result.textContent= "G.C.D of "+n1+" and "+n2+" is "+gcd+" \n";
}
 
 
var btnCalc=document.getElementById("btnCalc");
btnCalc.onclick=area;
</script>
    
</body>

<body>

</div>

function area(){

var n1=document.getElementById("b1").value;

var n2=document.getElementById("b2").value;

var result=document.getElementById("result");

n1=Number(n1);

n2=Number(n1);

let gcd = 1;

for(let i = 1; i <= n1 && i <= n2; ++i)

{

// Checks if i is factor of both integers

if(n1 % i==0 && n2 % i==0)

gcd = i;

}

result.textContent= "G.C.D of "+n1+" and "+n2+" is "+gcd+" \n";

}

var btnCalc=document.getElementById("btnCalc");

btnCalc.onclick=area;

</script>

</body>

Output:

Pseudocode to Find GCD of Two Numbers4 min read

Leave a Comment X

You may also like

Leave a Comment X