Find the Greatest Common Divisor (GCD) in C

Introduction

In this lab, you will learn how to find the Greatest Common Divisor (GCD) of two integers using the Euclidean algorithm in a C program. You will start by reading two integers from user input, then apply the Euclidean algorithm to calculate their GCD, and finally print the result. This lab covers fundamental concepts in number theory and discrete mathematics, providing a practical application of these principles using the C programming language.

Skills Graph

Read Two Integers

In this step, you will learn how to read two integers from user input in a C program to find their Greatest Common Divisor (GCD).

First, let's create a new C file for our GCD program:

cd ~/project
nano gcd.c

Now, add the following code to read two integers:

#include <stdio.h>

int main() {
    int num1, num2;

    printf("Enter the first integer: ");
    scanf("%d", &num1);

    printf("Enter the second integer: ");
    scanf("%d", &num2);

    printf("First number: %d\n", num1);
    printf("Second number: %d\n", num2);

    return 0;
}

Let's break down the code:

• scanf() is used to read integer input from the user
• %d is the format specifier for integers
• &num1 and &num2 pass the memory addresses of the variables to store the input

Compile and run the program:

gcc gcd.c -o gcd
./gcd

Example output:

Enter the first integer: 48
Enter the second integer: 18
First number: 48
Second number: 18

Apply Euclidean Algorithm

In this step, you will implement the Euclidean algorithm to find the Greatest Common Divisor (GCD) of two integers.

Open the previous gcd.c file and modify it to include the GCD calculation:

cd ~/project
nano gcd.c

Update the code with the Euclidean algorithm implementation:

#include <stdio.h>

// Function to calculate GCD using Euclidean algorithm
int calculateGCD(int a, int b) {
    // Ensure positive numbers
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;

    // Euclidean algorithm
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("Enter the first integer: ");
    scanf("%d", &num1);

    printf("Enter the second integer: ");
    scanf("%d", &num2);

    // Calculate GCD
    gcd = calculateGCD(num1, num2);

    printf("First number: %d\n", num1);
    printf("Second number: %d\n", num2);
    printf("Greatest Common Divisor: %d\n", gcd);

    return 0;
}

Let's break down the Euclidean algorithm implementation:

• The algorithm repeatedly divides the larger number by the smaller number
• It uses the modulo operator % to get the remainder
• The process continues until the remainder becomes 0
• The last non-zero remainder is the GCD

Compile and run the program:

gcc gcd.c -o gcd
./gcd

Example output:

Enter the first integer: 48
Enter the second integer: 18
First number: 48
Second number: 18
Greatest Common Divisor: 6

Print the GCD

In this step, you will format and print the GCD result with additional context to make the output more informative.

Open the previous gcd.c file and add some formatting to the output:

cd ~/project
nano gcd.c

Update the code to enhance the GCD output:

#include <stdio.h>

// Function to calculate GCD using Euclidean algorithm
int calculateGCD(int a, int b) {
    // Ensure positive numbers
    a = (a > 0) ? a : -a;
    b = (b > 0) ? b : -b;

    // Euclidean algorithm
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

int main() {
    int num1, num2, gcd;

    printf("Greatest Common Divisor (GCD) Calculator\n");
    printf("----------------------------------------\n");

    printf("Enter the first integer: ");
    scanf("%d", &num1);

    printf("Enter the second integer: ");
    scanf("%d", &num2);

    // Calculate GCD
    gcd = calculateGCD(num1, num2);

    // Formatted output
    printf("\nResults:\n");
    printf("First number:  %d\n", num1);
    printf("Second number: %d\n", num2);
    printf("GCD:           %d\n", gcd);

    // Additional explanation
    printf("\nExplanation:\n");
    printf("The Greatest Common Divisor (GCD) is the largest positive integer\n");
    printf("that divides both numbers without leaving a remainder.\n");

    return 0;
}

Compile and run the program:

gcc gcd.c -o gcd
./gcd

Example output:

Greatest Common Divisor (GCD) Calculator
----------------------------------------
Enter the first integer: 48
Enter the second integer: 18

Results:
First number:  48
Second number: 18
GCD:           6

Explanation:
The Greatest Common Divisor (GCD) is the largest positive integer
that divides both numbers without leaving a remainder.

Key improvements:

• Added a title and separator
• Formatted the output with aligned columns
• Included an explanation of GCD concept
• Maintained the core GCD calculation logic

Summary

In this lab, you first learned how to read two integers from user input using the scanf() function. You then implemented the Euclidean algorithm to calculate the Greatest Common Divisor (GCD) of the two numbers. The Euclidean algorithm is an efficient way to find the GCD by repeatedly applying the modulo operation until the remainder becomes zero, at which point the GCD is the last non-zero remainder. Finally, you printed the calculated GCD.