# GCD (Greatest Common Division) of two numbers

**GCD (Greatest Common Division) of two numbers**

**Problem Definition:** To find the Greatest Common Divisor (GCD)of two numbers.

**Problem Analysis:** GCD of two numbers is the greatest common factor of the given two numbers.

GCD of two numbers is obtained using the following method: Divide the larger of the two numbers by the smaller one.

Divide the divisor by the remainder.

Repeat this process till the remainder becomes zero.

The last divisor is the GCD of the two.

**Solving by Example:** Consider two numbers 188 and 423.

The smaller number is 188.Therefore divide 423 by 188.

**Step 1**

47(Remainder) becomes the divisor and 188 (Divisor) becomes the dividend.

**Step 2**

Since the remainder has become zero, 47 is the GCD of 188 and 423.

**Algorithm Definition**

Step 1: Start

Step 2: Read two numbers for which GCD is to be found, say (a,b).

Step 3: Let a be the larger of the two numbers.

Step 4: Divide a by b.

Step 5: Get the remainder of the division operation.

Step 6: Divide the divisor of the previous division operation with the remainder.

Step 7: Repeat steps 4,5,6 till the remainder become zero.

Step 8: The divisor of the last division operation performed is the GCD of the two numbers.

Step 9: Stop

**Question. What is algorithm? Write the characteristics of an algorithm. Give an example for algorithm. **

**Answer :**

**Definition of Algorithm**

Algorithm is a step by step solution to a given problem. Sequence of steps written in order to carry out some particular task. Each step of an algorithm is written in english.

Various characteristics of an algorithm are

- The algorithm must have definite start and end.
- An algorithm may accept zero or more inputs
- An algorithm must produce at least one output
- The steps of an algorithm must be simple, easy to understand and unambiguous.
- Each step must be precise and accurate.
- The algorithm must contain finite number of steps.

**Example:**

**Algorithm 1: Algorithm for finding of area of triangle**

Step 1: start

Step 2: Read base and height of traingle

Step 3: Calulate area of traingle

Step 4: print area of traingle

Step 5: stop

**Algorithm 2: Algorithm for finding of sum and average of given three numbers**

Step 1: start

Step 2: Read three numbers i.e. A, B and C

Step 3: find sum of three numbers i.e. sum=A+B+C

Step 4: find average of three numbers i.e. average=sum/3

Step 4: print sum and average

Step 5: stop

**Question : What is pseudocode? Give an example for pseudocode. **

**Answer:**

**Definition of Pseudocode**

Pseudocode is high level description of an algorithm that contains a sequence of steps written in combination of english and mathematical notations to solve a given problem.

Pseudocode is part english and part program logic. Pseudocodes are better than algorithm since it contains ordered steps and mathematical notations they are more closer to the statements of programming language.

This is essentially an intermediate-step towards the development of the actual code(program). Although pseudo code is frequently used, there are no set of rules for its exact writing.

**Example:**

**Pseudocode 1: Pseudocode for finding area of traingle**

Pseudocode Area_of_Traingle

BEGIN

READ base and Height

CALCULATE Area_of_Triangle=(base*height)/2

PRINT Area_of_Triangle

END

**Pseudocode 2:Pseudocode for finding sum and average of three numbers**

Pseudocode SUM_AVG

BEGIN

READ A, B, and C

CALCULATE sum=A+B+C

CALCULATE average=SUM/3

PRINT sum and average

END

**Question : What is flowchart? List and define the purpose of symbols used to
represent flowchart. Give an example for flowchart.**

**Answer :**

**Definition of flowchart**

Flowchart is a graphical or pictorial representation of an algorithm. Its a program "design tool in which standard graphical symbols are used to represent the logical flow of data through a function.

Flowchart is a combination of symbols. They show start and end points, the order and sequence of actions, and how one part of a flowchart is connected to another.

**Example:**

**Finding the area of triangle **