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?

The answer is actually correct, because the GCD of 4 and 1 is 1. Please note that you only use the first character of 16, so 16 becomes 1. — Xaver, Dec 19 '20 at 20:10
`if (argc < 2) return 1;` should be `if (argc < 3) return 1;` `argv[0] is always the program name — ryyker, Dec 19 '20 at 20:10
Read documentation of your C compiler (e.g. [GCC](http://gcc.gnu.org/)) and debugger (e.g. [GDB](https://www.gnu.org/software/gdb/)...) — Basile Starynkevitch, Dec 19 '20 at 20:11

score 3 · Answer 1 · answered Dec 19 '20 at 20:11

3

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.

answered Dec 19 '20 at 20:11

dbush

205,898
23
218
273

Actually, use [atoi](https://en.cppreference.com/w/c/string/byte/atoi) – Basile Starynkevitch Dec 19 '20 at 20:12
@BasileStarynkevitch you probably should use sscanf or strtol instead: https://stackoverflow.com/questions/3420629/what-is-the-difference-between-sscanf-or-atoi-to-convert-a-string-to-an-integer – Dock Dec 19 '20 at 21:03

ryyker · Answer 2 · 2020-12-19T22:26:39.043

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;
}

C program for computing greatest common divisor gives wrong answer

2 Answers2