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编写。代码如下：
packagemainimport("fmt""math/rand""time")funcmain(){rand.Seed(time.Now().Unix())count:=0constTOTAL=100fori:=0;i<TOTAL;i++{arr:=genRandArr()ret1:=IsTwoTwoPrime1(arr)ret2:=IsTwoTwoPrime2(arr)ret3:=IsTwoTwoPrime3(arr)ifret1==ret2&&ret1==ret3{count++}fmt.Println(ret1,ret2,ret3,arr)}fmt.Println("总数：",TOTAL)fmt.Println("正确数：",count)}funcgenRandArr()[]int{arrLen:=rand.Intn(5)+5arr:=make([]int,arrLen)fori:=0;i<arrLen;i++{arr[i]=rand.Intn(1000)+2}returnarr}funcIsTwoTwoPrime1(arr[]int)bool{iflen(arr)<=1{returntrue}fori:=0;i<len(arr)-1;i++{forj:=i+1;j<len(arr);j++{ifGcd(arr[i],arr[j])>1{returnfalse}}}returntrue}funcIsTwoTwoPrime2(arr[]int)bool{iflen(arr)<=1{returntrue}temp:=arr[0]fori:=1;i<len(arr);i++{ifGcd(temp,arr[i])>1{returnfalse}temp*=arr[i]}returntrue}funcIsTwoTwoPrime3(arr[]int)bool{iflen(arr)<=1{returntrue}primeSet:=make(map[int]struct{})fori:=0;i<len(arr);i++{temp:=arr[i]primeTempSet:=make(map[int]struct{})forj:=2;j*j<=arr[i];{iftemp%j==0{temp/=jprimeTempSet[j]=struct{}{}}else{iftemp==1{break}j+=1}}iftemp!=1{primeTempSet[temp]=struct{}{}}forprimeTemp,_:=rangeprimeTempSet{if_,ok:=primeSet[primeTemp];ok{returnfalse}else{primeSet[primeTemp]=struct{}{}}}}returntrue}//最大公约数：【辗转相除法】funcGcd(aint,bint)int{//迭代forb!=0{a,b=b,a%b}returna}执行结果如下：
