Convert the array such that the GCD of the array becomes 1 in C++

In this tutorial, we will be discussing a program to convert the array such that the GCD of the array becomes one.

For this we will be provided with an array and a positive integer k. Our task is to convert the array elements such that the GCD of elements is 1 while only dividing the array elements by k any number of times until the element is less than k.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; //calculating the GCD of array int calculate_gcd(int* arr, int n){    int gcd = arr[0];    for (int i = 1; i < n; i++)       gcd = __gcd(arr[i], gcd);    return gcd; } //checking if the operation is possible bool convertGcd(int* arr, int n, int k){    int gcd = calculate_gcd(arr, n);    int max_prime = 1;    for (int i = 2; i <= sqrt(gcd); i++) {       while (gcd % i == 0) {          gcd /= i;          max_prime = max(max_prime, i);       }    }    max_prime = max(max_prime, gcd);    return (max_prime <= k); } int main(){    int arr[] = { 10, 15, 30 };    int k = 6;    int n = sizeof(arr) / sizeof(arr[0]);    if (convertGcd(arr, n, k) == true)    cout << "Yes";    else       cout << "No";    return 0; }

Output

Yes