数据结构
网络
关系型数据库管理系统
操作系统
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+ 浏览量
广告