c - find lowest common multiple

Question

Here I am trying to find lowest common multiple of an array of numbers. I used the following formula to find the value which uses greatest common divisor to find out LCM.

My program calculates GCD correctly, but when it comes to find out LCM using GCD it gives wrong LCM value. What might be wrong in my logic. Any help would be much appreciated.

#include <stdio.h>

int main() {
   int arr[10] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
   int GCD = findGCD(arr[0], arr[1]);
   int LCM = (arr[0] * arr[1]) / GCD;
   int i;
   for (i = 2; i < sizeof(arr) / sizeof(arr[0]); i++) {
        int temp = GCD;
        GCD = findGCD(temp, arr[i]);
        LCM = (temp * arr[i]) / GCD;
   }
   printf("GCD IS %d AND LCM IS %d", GCD, LCM);
}

int findGCD(int num1, int num2) {
    if (num2 == 0) {
        return num1;
    }
    if (num1 % num2 == 0) {
        return num2;
    }
    return findGCD(num2, num1 % num2);
}

Answer 1

これは役に立ちますか？それとも、findGCD の呼び出し回数をできるだけ少なくしながら、GCD と LCM を計算することが目的でしたか?

int main(){
   int arr[10]={10,20,30,40,50,60,70,80,90,100};
   int GCD=arr[0];
   int LCM=arr[0];
   int i;

   for(i=1;i<sizeof(arr)/sizeof(arr[0]);i++){
        GCD = findGCD(GCD,arr[i]);
        LCM = (LCM * arr[i]) / findGCD(LCM, arr[i]);
   }

   printf("GCD IS %d AND LCM IS %d",GCD,LCM);
}

Answer 2

コードには複数の問題があります。

• 配列のすべての要素の LCM を計算しますが、GCD は 2 つの初期値についてのみ計算します。

• 乗算式は、GCD で除算する前にオーバーフローする可能性があります。逆の順序で操作を実行し、潜在的なオーバーフローをチェックする必要があります。

• のプロトタイプfindGCDが正しくありません: を返しますint。

修正版は次のとおりです。

#include <limits.h>
#include <stdio.h>

int findGCD(int num1, int num2) {
    if (num2 == 0) {
        return num1;
    }
    if (num1 % num2 == 0) {
        return num2;
    }
    return findGCD(num2, num1 % num2);
}

int main() {
    int arr[10] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
    int GCD = arr[0];
    int LCM = arr[0];
    size_t i;

    for (i = 1; i < sizeof(arr) / sizeof(arr[0]); i++) {
        if (LCM == 0 || arr[i] == 0) {
            LCM = 0;
            break;
        }
        GCD = findGCD(GCD, arr[i]);
        LCM = LCM / findGCD(LCM, arr[i]);
        if (arr[i] > INT_MAX / LCM) {
            printf("integer overflow: the LCM exceeds the range of type int\n");
            return 1;
        }
        LCM = LCM * arr[i];
    }
    printf("GCD IS %d AND LCM IS %d", GCD, LCM);
    return 0;
}