[Solved] Most efficient method of finding the number of common factors of two numbers

by


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", 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))

}

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
}

1

solved Most efficient method of finding the number of common factors of two numbers