顺便说一下,另一个算法是先分解质因数,然后通过对因子及其幂次的映射进行递归,找到所有可能的除数。
当 n 变大时,例如 n = 100_000
,这种方法可以更快。
代码(go
)
amicable_number.go:
package p21
import (
"math"
)
func FindAmicableNumberSum(n int, excludeSame bool) int {
dm := FindAmicableNumber(n, excludeSame)
sum := 0
for k, v := range dm {
if k != v {
sum += k
}
}
return sum
}
func FindAmicableNumber(n int, excludeSame bool) map[int]int {
dsm := FindAllDivisorSum(n)
am := make(map[int]int)
for k, v := range dsm {
if v2, ok := dsm[v]; ok && k == v2 {
if excludeSame && k == v {
continue
}
am[k] = v
am[v] = k
}
}
return am
}
func FindAllDivisorSum(n int) map[int]int {
ps := FindPrimeTillN(n + 1)
dm := make(map[int]int)
for x := 2; x < n; x++ {
ks, fm := findFactorMap(x, ps)
sum := divisorSum(ks, fm) - x
dm[x] = sum
}
return dm
}
func FindDivisorSum(x int) int {
ps := FindPrimeTillN(x + 1)
ks, fm := findFactorMap(x, ps)
return divisorSum(ks, fm) - x
}
func findFactorMap(x int, ps []int) ([]int, map[int]int) {
fm := make(map[int]int)
var ks []int
for i := 0; i < len(ps) && x > 1; i++ {
p := ps[i]
e := 0
for x%p == 0 {
x /= p
e++
}
if e > 0 {
ks = append(ks, p)
fm[p] = e
}
}
return ks, fm
}
func divisorSum(ks []int, fm map[int]int) int {
if len(ks) == 1 {
p := ks[0]
e := fm[p]
sum := 1
for i, d := 1, p; i <= e; i, d = i+1, d*p {
sum += d
}
return sum
}
fp := ks[0]
fe := fm[fp]
if fe == 0 {
delete(fm, fp)
result := divisorSum(ks[1:], fm)
fm[fp] = fe
return result
} else if fe == 1 {
delete(fm, fp)
result := (fp + 1) * divisorSum(ks[1:], fm)
fm[fp] = fe
return result
} else {
fm[fp]--
right := divisorSum(ks, fm)
fm[fp]++
delete(fm, fp)
left := int(math.Pow(float64(fp), float64(fe))) * divisorSum(ks[1:], fm)
fm[fp] = fe
return left + right
}
}
func FindPrimeTillN(n int) []int {
var ps []int
outer:
for x := 2; x < n; x++ {
max := int(math.Sqrt(float64(x)))
for i := 0; i < len(ps) && ps[i] <= max; i++ {
if x%ps[i] == 0 {
continue outer
}
}
ps = append(ps, x)
}
return ps
}
amicable_number_test.go (测试用例):
package p21
import (
"fmt"
"github.com/stretchr/testify/assert"
"testing"
)
func TestFindAmicableNumberSum(t *testing.T) {
sumExcludeSame := FindAmicableNumberSum(10_000, false)
fmt.Printf("10000 (include same = %v) -> sum: %d\n", false, sumExcludeSame)
assert.Equal(t, 31626, sumExcludeSame)
}
func TestFindAmicableNumberSumLarge(t *testing.T) {
}
func TestFindAmicableNumber(t *testing.T) {
fmt.Printf("10_000 (include same = %v) -> pairs: %d\n", true, FindAmicableNumber(10_000, true))
fmt.Printf("10_000 (include same = %v) -> pairs: %d\n", false, FindAmicableNumber(10_000, false))
}
func TestFindDivisorSum(t *testing.T) {
fmt.Printf("30 -> %d\n", FindDivisorSum(30))
fmt.Printf("220 -> %d\n", FindDivisorSum(220))
fmt.Printf("284 -> %d\n", FindDivisorSum(284))
fmt.Printf("1184 -> %d\n", FindDivisorSum(1184))
fmt.Printf("1210 -> %d\n", FindDivisorSum(1210))
}
要运行测试,需要通过以下方式添加testify
:
go get -u github.com/stretchr/testify
速度
这比问题中使用的蛮力方法要快得多,以下是我的测试结果(在一台旧笔记本上运行):
- 使用分解因数和递归(即上面的代码):
- n =
10_000
,sum = 31626
,耗时0.02
秒。
- n =
100_000
,sum = 852810
,耗时0.97
秒。
- n =
1_000_000
,sum = 25275024
,耗时57
秒。
我认为它可以进一步优化,因为对于1_000_000
来说仍然很慢。
- 使用暴力方法(即与问题中类似的代码):
- n =
10_000
,sum = 31626
,耗时0.38
秒。
- n =
100_000
,sum = 852810
,耗时38
秒。
- n =
1_000_000
,时间太长,我在完成之前停止了。
提示
- 函数
FindAmicableNumberSum()
接受一个标志excludeSame
,用于指示是否排除使d(n) = n
的数字。
对于Project Euler#21
,它应始终设置为true
。