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 (fmtmath/randtime)func main() {rand.Seed(time.Now().Unix())count := 0const TOTAL = 100for i := 0; iTOTAL; i++ {arr := genRandArr()ret1 := IsTwoTwoPrime1(arr)ret2 := IsTwoTwoPrime2(arr)ret3 := IsTwoTwoPrime3(arr)if ret1 == ret2 总数：, TOTAL)fmt.Println(正确数：, count)}func genRandArr() []int {arrLen := rand.Intn(5) + 5arr := make([]int, arrLen)for i := 0; iarrLen; i++ {arr[i] = rand.Intn(1000) + 2}return arr}func IsTwoTwoPrime1(arr []int) bool {if len(arr) = 1 {return true}for i := 0; ilen(arr)-1; i++ {for j := i + 1; jlen(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; ilen(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; ilen(arr); i++ {temp := arr[i]primeTempSet := make(map[int]struct{})for j := 2; j*j = arr[i]; {if temp%j == 0 {temp /= jprimeTempSet[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}执行结果如下：
