Question

Consider the following C codes to compute the gcd of two integers.

/// code 1

#include <stdio.h>

int gcd(int a, int b) {

    while (a != b) {

        if (a > b) a = a - b;

        else b = b - a;

    }

    return a;

}

/// code 2

#include <stdio.h>

int getint() {

    int i;

    scanf("%d", &i);

    return i;

}

void putint(int i) {

    printf("%d\n", i);

}

int main() {

    int i = getint(), j = getint();

    while (i != j) {

        if (i > j) i = i % j;  

        else j = j % i;

    }

    putint(i);

}

Do code 1 and code 2 work correctly? Why and why not? Can you fix the one(s) not working (if any?) Which one is faster? Explain.

Answer 1

Code1:- will work perfectly no issue but it will take more time for one smaller number and one larger number only that is disadvantage.

Code2:- there is some mistake in that Code-2 while condition is wrong the code is turing to fall in infinite loop

Coorect Code2:-

#include<stdio.h>

int getint()

{

int i;

scanf("%d",&i);

return i;

}

void putint(int i)

{

printf("%d",i);

}

int main()

{

int i=getint();int j=getint(),temp;

while(i!=0)

{

if(i>j)

{

temp=i;

i=j;

j=temp;

}

int x=i;

i=j%i;

j=x;

}

putint(j);

}

int main () int i-getint);int j-getint,temp; lh lh while (i!-0) if(i>j) temp-i i-j j-temp int x-i; putint (5)

Code2 will fast because we are not doing repetetion substractions and we are doing modular division