douyu9012
douyu9012
2019-03-11 07:28

查找两个数的公因数的最有效方法

  • math
已采纳

I have two numbers for example the numbers are 12 and 16.

factors of 12 are 1, 2, 3, 4, 6, 12

factors of 16 are 1, 2, 4, 8, 16

common factors of these two numbers are 1, 2 and 4.

So the number of common factors are 3. I need to build a Go program for finding the number common factors of two numbers. But the program should be efficient and with minimum number of loops or without loops. I will provide my code and you can also contribute and suggest with another best methods.

package main

import "fmt"

var (
    fs    []int64
    fd    []int64
    count int
)

func main() {
    commonFactor(16, 12)
    commonFactor(5, 10)
}

func commonFactor(num ...int64) {
    count = 0
    if num[0] < 1 || num[1] < 1 {
        fmt.Println("
Factors not computed")
        return
    }
    for _, val := range num {
        fs = make([]int64, 1)
        fmt.Printf("
Factors of %d: ", val)
        fs[0] = 1
        apf := func(p int64, e int) {
            n := len(fs)
            for i, pp := 0, p; i < e; i, pp = i+1, pp*p {
                for j := 0; j < n; j++ {
                    fs = append(fs, fs[j]*pp)
                }
            }
        }
        e := 0
        for ; val&1 == 0; e++ {
            val >>= 1
        }
        apf(2, e)
        for d := int64(3); val > 1; d += 2 {
            if d*d > val {
                d = val
            }
            for e = 0; val%d == 0; e++ {
                val /= d
            }
            if e > 0 {
                apf(d, e)
            }
        }
        if fd == nil {
            fd = fs
        }
        fmt.Println(fs)
    }
    for _, i := range fs {
        for _, j := range fd {
            if i == j {
                count++
            }
        }
    }
    fmt.Println("Number of common factors =", count)
}

Output is :

Factors of 16: [1 2 4 8 16] Factors of 12: [1 2 4 3 6 12]

Number of common factors = 3

Factors of 5: [1 5] Factors of 10: [1 2 5 10]

Number of common factors = 2

Goplayground

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • dongxuan2577 dongxuan2577 2年前

    Answer 1, with no loops just recursion

    package main
    
    import (
        "fmt"
        "os"
        "strconv"
    )
    
    func factors(n int, t int, res *[]int) *[]int {
        if t != 0 {
            if (n/t)*t == n {
                temp := append(*res, t)
                res = &temp
            }
            res = factors(n, t-1, res)
        }
        return res
    }
    
    func cf(l1 []int, l2 []int, res *[]int) *[]int {
        if len(l1) > 0 && len(l2) > 0 {
            v1 := l1[0]
            v2 := l2[0]
            if v1 == v2 {
                temp := append(*res, v1)
                res = &temp
                l2 = l2[1:]
            }
            if v2 > v1 {
                l2 = l2[1:]
            } else {
                l1 = l1[1:]
            }
            res = cf(l1, l2, res)
        }
        return res
    }
    
    func main() {
        n, err := strconv.Atoi(os.Args[1])
        n2, err := strconv.Atoi(os.Args[2])
        if err != nil {
            fmt.Println("give a number")
            panic(err)
        }
        factorlist1 := factors(n, n, &[]int{})
        factorlist2 := factors(n2, n2, &[]int{})
        fmt.Printf("factors of %d %v
    ", n, factorlist1)
        fmt.Printf("factors of %d %v
    ", n2, factorlist2)
        common := cf(*factorlist1, *factorlist2, &[]int{})
        fmt.Printf("number of common factors = %d
    ", len(*common))
    
    }
    

    However, this blows up with larger numbers such as 42512703

    replacing the func that do the work with iterative versions can cope with bigger numbers

    func factors(n int) []int {
            res := []int{}
            for t := n; t > 0; t-- {
                    if (n/t)*t == n {
                            res = append(res, t)
                    }
            }
            return res
    }
    
    func cf(l1 []int, l2 []int) []int {
            res := []int{}
            for len(l1) > 0 && len(l2) > 0 {
                    v1 := l1[0]
                    v2 := l2[0]
                    if v1 == v2 {
                            res = append(res, v1)
                            l2 = l2[1:]
                    }
                    if v2 > v1 {
                            l2 = l2[1:]
                    } else {
                            l1 = l1[1:]
                    }
            }
            return res
    }
    
    点赞 评论 复制链接分享