Algorithm and flowchart to check whether two numbers are coprime or not

[2446 views]

What are Co-prime Numbers?

Co-prime numbers are the numbers that have only 1 as a common factor between them. In other words, the highest common factor of the numbers will always be 1. They are also known as mutually prime or relatively prime numbers. For example: (3,5), (14,15), (11,13), (2,7), etc.

Let us consider the example of 5,6:
Factors of 5: 1,5.
Factors of 6: 1, 2, 3, 6.
Common factors: 1
Therefore, 5 and 6 are co-prime.

It is important to note that it is not necessary that both the numbers have to be prime in a co-prime number pair. For example: (2,9), (2,15), (4,13), (4,15), etc. Here, in each pair of numbers, there is one prime and one non-prime number.

In this article, we will learn how to check whether two given numbers are coprime numbers or not, with the help of an algorithm and flowchart. In this algorithm, we will use the concept of HCF to find out the common factors between the given numbers.

Algorithm to check two numbers are coprime number or not:

Step 1: Start Step 2: Read the first number to be checked as user input: n1 Step 3: Read the second number to be checked as user input: n2 Step 4: Initialize hcf of two numbers as 1 Step 5: Initialize loop variable i as 2 Step 6: WHILE i < n1 AND i < n2 DO: 6.1: IF n1%i = 0 AND n2%i = 0, THEN: 6.1.a: hcf = i 6.1.b: Exit from the loop 6.2: END IF Step 7: END WHILE Step 8: IF hcf = 1, THEN: 8.1: Display “Co-prime Numbers” Step 9: ELSE: 9.1: Display “Not co-prime Numbers” Step 10: End IF-ELSE Step 11: Stop

Explanation:

In this algorithm, we need to check whether two given numbers are co-prime or not. To do so, we need to find out the common factors between the two numbers. Here, we use the concept of HCF. Two numbers are co-prime if their HCF is equal to 1. We apply this concept to our algorithm.

The algorithm starts off by taking the two numbers to be checked as user input. We store these values into two variables: say n1 and n2. We initialize the HCF of the two numbers as 1. To calculate the HCF, we start a loop that runs from 1 until loop variable is greater than n1 or n2, whichever is smaller. In each iteration, we check whether i is divisible by n1 as well as n2. If both the numbers are divisible by i, this means there is a common factor between the numbers. HCF will then become that common factor. We exit from the loop and check whether the hcf is equal to one or not. If it is one, we display "co-prime numbers", else, we display "not co-prime numbers".