資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究在C++中將陣列轉換為使陣列的GCD為1的陣列
在本教程中，我們將討論一個將陣列轉換為陣列的GCD為1的程式。
為此，我們將獲得一個數組和一個正整數k。我們的任務是轉換陣列元素，使得元素的GCD為1，同時僅將陣列元素除以k任意次數，直到元素小於k。
例如
#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;
}輸出
Yes
更新日期：2020年1月22日
229次瀏覽
廣告