資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式檢查給定數字是否互質
假設，我們在一個數組nums中有n個整數。我們需要找出陣列中的數字是成對互質、集合互質還是不互質。
如果gcd(nums[i], nums[j]) = 1，則稱兩個數字nums[i]和nums[j]為成對互質。這應該適用於陣列中的每一對數字，並且i < j。
如果gcd(nums[i]) = 1，則稱這些數字為集合互質。
如果它們既不是成對互質也不是集合互質，我們就說它們不互質。
因此，如果輸入類似於n = 4，nums = {7, 11, 13, 17}，則輸出將是這些數字是成對互質的。
如果我們檢查陣列中的每一對數字，它們的gcd將始終為1。
為了解決這個問題，我們將遵循以下步驟：
Define an array fac of size: 100 initialized with 0s.
Define an array checkPrime of size: 100 initialized with 0s.
gcdVal := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
gcdVal := gcd of (nums[i], gcdVal)
(increase fac[nums[i]] by 1)
if gcdVal is same as 1, then:
pw := true
for initialize k := 2, when k < 100, update (increase k by 1), do:
if checkPrime[k] is non-zero, then:
Ignore following part, skip to the next iteration
c := 0
for initialize j := k, when j < 100, update j := j + k, do:
c := c + fac[j]
checkPrime[j] := true
pw := pw AND true if c <= 1
if pw is non-zero, then:
print("The numbers are pairwise coprime")
Otherwise
print("The numbers are setwise coprime")
Otherwise
print("The numbers are not coprime")示例
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int nums[]){
int fac[100] = {0};
bool checkPrime[100] = {0};
int gcdVal = 0;
for(int i = 0; i < n ; i++) {
gcdVal = __gcd(nums[i], gcdVal);
++fac[nums[i]];
}
if(gcdVal == 1) {
bool pw = true;
for(int k = 2; k < 100; ++k) {
if(checkPrime[k])
continue;
int c = 0;
for(int j = k; j < 100; j += k) {
c += fac[j];
checkPrime[j] = true;
}
pw = pw && c <= 1;
}
if(pw)
cout<< "The numbers are pairwise coprime";
else
cout<< "The numbers are setwise coprime";
}
else
cout << "The numbers are not coprime";
}
int main() {
int n = 4, nums[] = {7, 11, 13, 17};
solve(n, nums);
return 0;
}輸入
4, {7, 11, 13, 17};
輸出
The numbers are pairwise coprime
更新於: 2022年3月2日
2K+ 瀏覽量
廣告