2021-05-31：怎么判斷n個數倆倆互質？比如7,8,9任意兩個數更大公約數是1，所以7,8,9兩兩互質 。比如8,9,10不是兩兩互質，因為8和10的更大公約數是2 。
福大大 答案2021-05-31：
*** 一：兩兩判斷更大公約數是否為1 。時間復雜度是O(N^2) 。
*** 二：求乘積，然后求更大公約數 ?？雌饋頃r間復雜度是O(N)，但求乘積的代價非常大，不如 *** 一 。
*** 三：遍歷數組，求每個元素的質因數，然后存map 。下一個元素求質因數，如果map里已經存在，說明不是兩兩互質了 。時間復雜度O(N) ?？臻g復雜度O(質因數個數) 。對于小整數，此 *** 很不錯 。對于大整數，不如 *** 一 。
代碼用golang編寫 。代碼如下：
package mainimport ("fmt""math/rand""time")func main() {rand.Seed(time.Now().Unix())count := 0const TOTAL = 100for 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) + 5arr := 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 /= 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}執行結果如下：
文章插圖
【互質是什么意思互質】
推薦閱讀
- 慕強心理的意思 慕強心理什么意思
- 孕婦夢見好多蘑菇是什么意思 孕婦夢見好多蘑菇
- 榮辱與共的意思是什么意思 榮辱與共的意思
- 燃氣泄漏是什么味道
- 新年四件套是什么
- 蝦下面那條線是什么
- 王者kda是什么意思 王者kda的意思
- 計算機哪個鍵是清除鍵 計算器的清除鍵是什么字母
- 嬲嫐是什么意思怎么讀 嬲嫐是什么意思
- 夢見好幾頭牛是什么意思 夢見好幾頭牛