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}

執行結果如下：