日本免费全黄少妇一区二区三区-高清无码一区二区三区四区-欧美中文字幕日韩在线观看-国产福利诱惑在线网站-国产中文字幕一区在线-亚洲欧美精品日韩一区-久久国产精品国产精品国产-国产精久久久久久一区二区三区-欧美亚洲国产精品久久久久

  1. 首頁(yè) > 云知道 > >

互質(zhì) 互質(zhì)是什么意思啊

云知道


互質(zhì) 互質(zhì)是什么意思啊


2021-05-31：怎么判斷n個(gè)數(shù)倆倆互質(zhì)？比如7,8,9任意兩個(gè)數(shù)最大公約數(shù)是1，所以7,8,9兩兩互質(zhì) 。比如8,9,10不是兩兩互質(zhì)，因?yàn)?和10的最大公約數(shù)是2 。
【互質(zhì) 互質(zhì)是什么意思啊】福大大 答案2021-05-31：
方法一：兩兩判斷最大公約數(shù)是否為1 。時(shí)間復(fù)雜度是O(N^2) 。
方法二：求乘積，然后求最大公約數(shù) 。看起來(lái)時(shí)間復(fù)雜度是O(N) ， 但求乘積的代價(jià)非常大 ， 不如方法一 。
方法三：遍歷數(shù)組，求每個(gè)元素的質(zhì)因數(shù)，然后存map 。下一個(gè)元素求質(zhì)因數(shù)，如果map里已經(jīng)存在，說(shuō)明不是兩兩互質(zhì)了 。時(shí)間復(fù)雜度O(N) 。空間復(fù)雜度O(質(zhì)因數(shù)個(gè)數(shù)) 。對(duì)于小整數(shù)，此方法很不錯(cuò) 。對(duì)于大整數(shù)，不如方法一 。
代碼用golang編寫(xiě) 。代碼如下：
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("總數(shù)：", TOTAL)fmt.Println("正確數(shù)：", 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}//最大公約數(shù)：【輾轉(zhuǎn)相除法】func Gcd(a int, b int) int {//迭代for b != 0 {a, b = b, a%b}return a}執(zhí)行結(jié)果如下：


    推薦閱讀