计算C ++中GCD 1的子序列数

我们给了一个整数元素数组，任务是从给定数组中找出GCD为1的子序列。GCD是两个或多个整数的最大公约数，该整数将给定数字完全除，并且在所有数字中最大。

输入− int arr [] = {3，4，8，16}

输出-GCD 1的子序列数为-7

说明-

从给定数组中GCD为1可以形成的子序列是(3,4)，(3,8)，(3,16)，(4,3)，（8、3），（16， 3），（3、4、8）

输入− int arr [] = {5，7，10}

输出-GCD 1的子序列数为-3

说明-

从给定数组中GCD为1可以形成的子序列是(5,7)，(7,10)，(5,7,10)

以下程序中使用的方法如下

• 输入任意给定大小的整数元素数组。

• 计算数组的大小并将数据传递给函数以进行进一步处理

• 声明一个临时变量计数以存储GCD为1的子序列数

• 从i到0开始循环直到数组大小

• 在循环内部，从j到0直到数组大小开始另一个循环FOR

• 在循环内，检查IF GCD（arr [i]，arr [j]）= TRUE，然后将计数加1

• 返回计数

• 打印结果。

示例

# include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
   if (a == 0)
      return b;
   return gcd(b % a, a);
}
int GCD_1(int arr[],int size){
   int count = 0;
   for(int i=0;i<size;i++){
      for(int j=0;j<=size;j++){
         if(gcd(arr[i],arr[j])==1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {3, 4, 8, 16};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of number of sub-sequences with GCD 1 are: "<<GCD_1(arr, size);
   return 0;
}

输出结果

如果我们运行上面的代码，它将生成以下输出-

Count of number of sub-sequences with GCD 1 are: 7