我有两个数字，例如数字是 12 和 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.

所以公因子的个数是 3。我需要编写一个围棋程序来求两个数的公因子。但是该程序应该是高效的并且循环次数最少或没有循环。 我将提供我的代码，您也可以贡献和建议其他最佳方法。

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("\nFactors not computed")
        return
    }
    for _, val := range num {
        fs = make([]int64, 1)
        fmt.Printf("\nFactors 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)
}

输出是:

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，没有循环只有递归

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", n, factorlist1)
    fmt.Printf("factors of %d %v\n", n2, factorlist2)
    common := cf(*factorlist1, *factorlist2, &[]int{})
    fmt.Printf("number of common factors = %d\n", len(*common))

}

然而，这会随着更大的数字(例如 42512703)爆炸

用迭代版本替换完成工作的函数可以处理更大的数字

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
}

关于go - 求两个数的公因数的最有效方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55097007/