[Legacy Content] This page contains very old information, which might not be valid anymore, they are only kept here for legacy purposes.
if you have any inquiries, feel free to contact me! Click here

Greatest Common Divisor

Created: Tuesday, 08 October 2013 Written by Ehab Eldeeb

Write a program that reads 2 numbers from the user and gets the greatest common divisor (GCD)

Greatest Common Divisor .. Highest Common Divisor .. Highest Common Factor
Those are all the same .. simply, the highest number that can divide the two numbers without fractions (remainder)

 

Let's have this explained as simple as possible

I will post two versions
- Version 1: Print all divisors
- Version 2: Print GCD only

 

Version 1

#include <stdio.h>
#include <conio.h>

int main(){
    int x,y,m,i;

    printf("Insert any two numbers to get their GCD: ");

    scanf("%d%d",&x,&y); // read the two numbers
    if(x>y) // get the higher number
        m=y;
    else
        m=x;
    for(i=m;i>=1;i--){ // decrementing for loop  from "m" (the bigger number) till 1
        if(x%i==0 && y%i==0){ // if the number divides the two numbers, print it out
            printf("\nthe number %d is a divisor of the two numbers", i);
// this will print out ALL divisors .. the first one is the highest
        }
    }
    getch();
    return 0;
}

Version 2

#include <stdio.h>
#include <conio.h>

int main(){
    int x,y,m,i;

    printf("Insert any two numbers to get their GCD: ");

    scanf("%d%d",&x,&y);
    if(x>y)
        m=y;
    else
        m=x;
    for(i=m;i>=1;i--){
        if(x%i==0 && y%i==0){
            printf("\nGCD of two numbers is : %d", i);
            break; // LOOK HERE!! break ends the loop after the first output (gets GCD only)
        }
    }
    getch();
    return 0;
}