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

Question

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

Answer 1

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
}