C program for computing greatest common divisor gives wrong answer

Question

I have written the following program that takes two numbers from the command line and returns the gcd of these numbers.

#include <stdio.h>

int to_int(char *input)
{
        return *input - '0';
}

int main(int argc, char *argv[])
{
        if (argc < 2) return 1;
        int a = to_int(argv[1]);
        int b = to_int(argv[2]);
        int i;
        int result;
        for (i = 1; i <= a && i <= b; i++) {
                if (a%i==0 && b%i==0) {
                        result = i;
                }
        }
        printf("%d\n", result);
        return 0;
}

However when I give it the numbers 4 and 16 it returns the answer 1. This is incorrect. The gcd of 4 and 16 is 4. However I cannot find what is wrong with my code. Other examples that I found on the internet seem to be using the same algorithm that I am using (test if both numbers are evenly divisable by i and if they are then the gcd is i).

Could somebody point me towards the mistake in my code?

Answer 1

Your to_int function isn't doing what you think.

The expression *input - '0' takes the character code of the first character in input and subtracts the character code of '0'. So the result is the number corresponding to the first character of the given string, not the whole string.

You need to perform this operation in a loop, multiplying the result by 10 before adding the value of the next digit.

Answer 2

Some additional suggestions: (read in-line comments)

    // if (argc < 2) return 1;//need argc to be 3
    // (argv[0] always contains program name)
    if (argc < 3) return 1;//test for num arguments
    if(!(is_num(argv[1]) && is_num(argv[2]))) return 1;//test for number
    int a = atoi(argv[1]);//when available use library functions
    int b = atoi(argv[2]);
    int max = a>b?a:b;// determine larger of two inputs
    int i;
    int result= 0;
    //for (i = 1; i <= a && i <= b; i++) {//this is backwards,count from largest 
    for (i = max; i >= 1 ; i--) {//start at max, then decrement i
        if (a%i==0 && b%i==0) {
            result = i;
            break;//break out of loop when solution found
        }
    }
    printf("%d\n", result);
    return 0;

If a support function is desired, create one to verify input is a number:

bool is_num(char *input)
{
    if(!input) return false;
    int len = strlen(input);
    if(!((input[0] == '-') || (input[0] == '+') || (isdigit(input[0])))) return false;
    for(int i = 1;i<len;i++)
    {
        if(!isdigit(input[i])) return false;
    }
    return true;
}