Smallest Multiple by GoLang

前端之家收集整理的这篇文章主要介绍了Smallest Multiple by GoLang前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

My answer gives a general algorithm to deal with this problem via golang,and it produces the smallest positive number that is evenly divisible by all of the numbers from 1 to N. However,the overflow problem should be considered well by yourself in case of big int. Any question or suggestion,feel free to contact me.

func SmallestMultiple(n int) int {
    primeLst := []int{}
    factorCntMap := make(map[int]int)

    for i := 2; i <= n; i++ {
        tag := true
        tmp := i
        for _,j := range primeLst {
            if tmp%j == 0 {
                tag = false
                cnt := 0
                for tmp%j == 0 {
                    tmp /= j
                    cnt++
                }
                if cnt > factorCntMap[j] {
                    factorCntMap[j] = cnt
                }
            } else if tmp == 1 {
                break
            }
        }
        if tag == true {
            primeLst = append(primeLst,i)
            factorCntMap[i] = 1
        }
    }

    res := 1
    for k,v := range factorCntMap {
        for i := 0; i < v; i++ {
            res *= k
        }
    }
    return res
}
原文链接:https://www.f2er.com/go/187974.html

猜你在找的Go相关文章