Tag: GCD

Lets write a C program to check whether two positive numbers entered by the user are Co-Prime numbers / Relative Prime Numbers or not.

Co-Prime numbers / Relative Prime Numbers: Two numbers are said to be co-prime or relative prime numbers if they do not have a common factor other than 1.

OR

Two numbers whose Greatest Common Divisor(GCD) is 1 are known as Co-Prime or Relative Prime Numbers.

Note: User entered numbers(to check for co-prime) do not require to be prime numbers.

Related Read:
C Program To Find Prime Number or Not using While Loop
C Program to Find Factors of a Number using For Loop

Prime Number: Any natural number which is greater than 1 and has only two factors i.e., 1 and the number itself is called a prime number.

Factors of a number: All the numbers which perfectly divide a given number are called as Factors of that number.

Logic To Find If Two Numbers are Co-Prime or Not

If user enters n1 = 8 and n2 = 15;

We find smallest number in these two numbers(8 and 15) and store it inside variable min. So min = 8;

n1 = 8;
n2 = 15;

1st Iteration
count = 2;

( n1 % count == 0 && n2 % count == 0 )
( 8 % 2 == 0 && 15 % 2 == 0 )
( true && false ) = false;

2nd Iteration
count = 3;

( n1 % count == 0 && n2 % count == 0 )
( 8 % 3 == 0 && 15 % 3 == 0 )
( false && true ) = false;

3rd Iteration
count = 4;

( n1 % count == 0 && n2 % count == 0 )
( 8 % 4 == 0 && 15 % 4 == 0 )
( true && false ) = false;

4th Iteration
count = 5;

( n1 % count == 0 && n2 % count == 0 )
( 8 % 5 == 0 && 15 % 5 == 0 )
( false && true ) = false;

5th Iteration
count = 6;

( n1 % count == 0 && n2 % count == 0 )
( 8 % 6 == 0 && 15 % 6 == 0 )
( false && false ) = false;

6th Iteration
count = 7;

( n1 % count == 0 && n2 % count == 0 )
( 8 % 7 == 0 && 15 % 7 == 0 )
( false && false ) = false;

7th Iteration
count = 8;

( n1 % count == 0 && n2 % count == 0 )
( 8 % 8 == 0 && 15 % 8 == 0 )
( true && false ) = false;

Exit For Loop
Since count = 8 and min = 8, control exits for loop.

We’ve checked the complete iteration of for loop and we can see that no common number perfectly divides both user entered numbers n1 and n2 i.e., 8 and 15. So (8, 15) are co-prime numbers or relative prime numbers.

Example for non co-prime number

If n1 = 12 and n2 = 15

Number 3 perfectly divides both n1 and n2 i.e., 12 and 15. So 12 and 15 have 2 common factors i.e., 1 and 3, hence (12, 15) are not co-prime or relative prime numbers.

Video Tutorial: C Program To Check If Two Numbers are Co-Prime or Not

Source Code: C Program To Find Two Numbers are Co-Prime or Not

#include<stdio.h>

int main()
{
    int n1, n2, min, count, flag = 1;

    printf("Enter 2 positive numbers\n");
    scanf("%d%d", &n1, &n2);

    min = n1 < n2 ? n1 : n2;

    for(count = 2; count <= min; count++)
    {
        if( n1 % count == 0 && n2 % count == 0 )
        {
            flag = 0;
            break;
        }
    }

    if(flag)
    {
        printf("%d and %d are co-prime\n", n1, n2);
    }
    else
    {
        printf("%d and %d are not co-prime\n", n1, n2);
    }

    return 0;
}

Output 1:
Enter 2 positive numbers
8
15
8 and 15 are co-prime

Output 2:
Enter 2 positive numbers
12
15
12 and 15 are not co-prime

Logic To Check If Two Numbers are Co-Prime or Not

User enters 2 positive numbers, we store those numbers in variables n1 and n2 respectively. We find the smallest number in it and store it inside variable min.

We initialize loop counter variable count to 2(as all the numbers are perfectly divisible by 1, so we skip number 1 and start with number 2). We iterate through the for loop until count value is less than or equal to min. We increment the value of count by one for each iteration of for loop.

Inside for loop we check if there are any common factors for n1 and n2.
n1 % count == 0 && n2 % count == 0
If there are any common factors, then those numbers entered by the user are not co-prime / relative prime numbers. If there are no common factors for those two numbers, then they are co-prime or relative prime numbers.

For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List

For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert