互质（互质是什么意思）

2021-05-31：怎么判断n个数俩俩互质？比如7,8,9任意两个数最大公约数是1，所以7,8,9两两互质。比如8,9,10不是两两互质，因为8和10的最大公约数是2。

福大大 答案2021-05-31：

方法一：两两判断最大公约数是否为1。时间复杂度是O(N^2)。

方法二：求乘积，然后求最大公约数。看起来时间复杂度是O(N)，但求乘积的代价非常大，不如方法一。

方法三：遍历数组，求每个元素的质因数，然后存map。下一个元素求质因数，如果map里已经存在，说明不是两两互质了。时间复杂度O(N)。空间复杂度O(质因数个数)。对于小整数，此方法很不错。对于大整数，不如方法一。

代码用golang编写。代码如下：

package mainimport ( "fmt" "math/rand" "time")func main() { rand.Seed(time.Now().Unix()) count := 0 const TOTAL = 100 for i := 0; i < TOTAL; i++ { arr := genRandArr() ret1 := IsTwoTwoPrime1(arr) ret2 := IsTwoTwoPrime2(arr) ret3 := IsTwoTwoPrime3(arr) if ret1 == ret2 && ret1 == ret3 { count++ } fmt.Println(ret1, ret2, ret3, arr) } fmt.Println("总数：", TOTAL) fmt.Println("正确数：", count)}func genRandArr() []int { arrLen := rand.Intn(5) + 5 arr := make([]int, arrLen) for i := 0; i < arrLen; i++ { arr[i] = rand.Intn(1000) + 2 } return arr}func IsTwoTwoPrime1(arr []int) bool { if len(arr) <= 1 { return true } for i := 0; i < len(arr)-1; i++ { for j := i + 1; j < len(arr); j++ { if Gcd(arr[i], arr[j]) > 1 { return false } } } return true}func IsTwoTwoPrime2(arr []int) bool { if len(arr) <= 1 { return true } temp := arr[0] for i := 1; i < len(arr); i++ { if Gcd(temp, arr[i]) > 1 { return false } temp *= arr[i] } return true}func IsTwoTwoPrime3(arr []int) bool { if len(arr) <= 1 { return true } primeSet := make(map[int]struct{}) for i := 0; i < len(arr); i++ { temp := arr[i] primeTempSet := make(map[int]struct{}) for j := 2; j*j <= arr[i]; { if temp%j == 0 { temp /= j primeTempSet[j] = struct{}{} } else { if temp == 1 { break } j += 1 } } if temp != 1 { primeTempSet[temp] = struct{}{} } for primeTemp, _ := range primeTempSet { if _, ok := primeSet[primeTemp]; ok { return false } else { primeSet[primeTemp] = struct{}{} } } } return true}//最大公约数：【辗转相除法】func Gcd(a int, b int) int { //迭代 for b != 0 { a, b = b, a%b } return a}

执行结果如下：