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 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
}
``````
点赞 评论 复制链接分享