Relatively Prime Degree


General Statement: For a set of 3 positive integers, determine the degree to which they are relatively prime.

DEGREE 0 – no relatively prime pairs
DEGREE 1 – 1 pair of relatively prime numbers
DEGREE 2 – 2 pairs of relatively prime numbers
DEGREE 3 – all 3 numbers are relatively prime

Input: The first line in the data set is an integer that represents the number of data collections that follow. Each data collection contains 3 integers.

Output: All letters are upper case.
The output is to be formatted exactly like that for the sample output given below.

Assumptions: The integers are in the range 1..500.

Discussion: Two integers are relatively prime if they have no common factors other than 1.

Sample Input:
3
4 2 12
5 7 10
3 4 5

Sample Output:
4 2 12 = DEGREE 0
5 7 10 = DEGREE 2
3 4 5 = DEGREE 3

Solutions :

#include <stdio.h>

int gcd (int x, int y)
{
    if ( y == 0 )
        return x;

    return gcd (y, x % y);
}

int main ()
{
    int dataset;
    scanf ("%d", &dataset);

    while( dataset-- ) {
        int a;
        int b;
        int c;

        scanf ("%d %d %d", &a, &b, &c);

        int degree = 0;

        if ( gcd (a, b) == 1 )
            degree++;

        if ( gcd (b, c) == 1 )
            degree++;

        if ( gcd (a, c) == 1 )
            degree++;

        printf ("%d %d %d = DEGREE %d\n", a, b, c, degree);
    }

    return 0;
}


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s