DAA - Find the GCD and LCM of n numbers where (n>=2).

Program

#include<stdio.h>
#include<limits.h>
#include <time.h>
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int findLCM(int a[], int n)
{
int ans = a[0];
for (int i = 1; i < n; i++)
ans = (((a[i] * ans)) / (gcd(a[i], ans)));
return ans;
}
int findGCD(int arr[], int n)
{
int result = arr[0];
for (int i = 1; i < n; i++)
{
result = gcd(arr[i], result);
if(result == 1)
{
return 1;
}
}
return result;
}
int main()
{
int n;
printf("Enter array length: ");
scanf("%d", &n);
int a[n];
printf("Enter array: ");
for(int i=0; i<n; i++)
scanf("%d", &a[i]);
clock_t start,end;
double total_cputime;
start=clock();
int gcd = findGCD(a, n);
end=clock();
total_cputime=((double)(end-start))/CLOCKS_PER_SEC;
printf("\nGCD: %d", gcd);
printf("\nTotal time taken: %lf\n\n", total_cputime);
start=clock();
int lcm = findLCM(a, n);
end=clock();
total_cputime=((double)(end-start))/CLOCKS_PER_SEC;
printf("LCM: %d", lcm);
printf("\nTotal time taken: %lf", total_cputime);
return 0;
}

Output

Check More Question:

• DAA- C program for Selection Sort to Compare Time Complexity Solved Question

• Program to Find Time Complexity of Sum Of contiguous subarray  within a one dimensional (1-D) array