-
Notifications
You must be signed in to change notification settings - Fork 0
/
lcm.go
50 lines (47 loc) · 1.62 KB
/
lcm.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// gogo. A Go (Golang) toolbox.
// Copyright (C) 2019-2023 Yuan Gao
//
// This file is part of gogo.
//
// gogo is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.
package mathalgo
import "github.com/donyori/gogo/constraints"
// LCM calculates the least common multiple of the integers xs.
//
// The least common multiple of non-zero integers is the smallest
// positive integer that is divisible by each of the integers.
// In particular, if there is at least one zero,
// the least common multiple is considered zero,
// since zero is the only common multiple of zero and other integers.
//
// According to the above definition,
// LCM always returns a non-negative value,
// and it returns 0 if and only if len(xs) is 0 or
// there is at least one 0 in xs.
func LCM[Int constraints.Integer](xs ...Int) Int {
if len(xs) == 0 {
return 0
}
for _, x := range xs {
if x == 0 {
return 0
}
}
lcm := absIntToUint64(xs[0])
for i := 1; i < len(xs); i++ {
x := absIntToUint64(xs[i])
lcm = lcm / gcd2Uint64Stein(lcm, x) * x
}
return Int(lcm)
}