鉴于昨天探讨的数学题本人收获颇丰，今天再发一道有意思的数学题，感兴趣的快进来试试

[YUX]

定义: d(n) 为 n 的所有除数之和(不包括 n 自身，最小为 1 )，例如:

• 220 的除数是 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 所以 d(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284

• 284 的除数是 1, 2, 4, 71, 142 所以 d(284) = 1 + 2 + 4 + 71 + 142 = 220

定义: 因为 d(220) = 284, d(284) = 220 所以 220 和 284 这两个数都被称为 友好数

Question 在小于一亿的数中，共有多少个友好数

---

• 我计算的答案是 467
• 昨天的题，欢迎继续讨论

[Ultraman]

这个问题实实在在让我认识到了电脑性能的差距。。。
算了好久才算了不到 200 个。。。

[Ultraman]

@Ultraman 当然还有我自己的菜🐔水平。。。

[YUX]

@Ultraman #21 前 1 千万才有 208 个 已经一个亿的 1/10 了 hhhhh 我更关心你是用那个语言写的

[Ultraman]

@YUX #23 C 语言。376s 才跑完前 1000 个，而且才算出来 200 个结果，还不知道哪里错了。感觉 c 语言白学了 QAQ
https://pastebin.com/embed_js/F1AiPK9F

[Ultraman]

@Ultraman #24 呸，是前 1kw 个

[input2output]

用 go 写了一个，速度还行，30 几秒的样子，就是不知道哪里出错了，算出来 432 个

[YUX]

@input2output #26 前一千万是 208 个么？

[shm7]

是不是可以把质数算出来，然后用小的非质数做 线性规划

[input2output]

@input2output #26 把 uint32 改成 uint64 就好了，就是慢了好多；算下来是 462 ？
和 @luckyrayyy #11 一样
如果 a 可以等于 b，那算下来就是 467 了

[Ultraman]

@Ultraman #24 long 改成 int 时间缩短一多半也还得 111S 。

[luckyrayyy]

@input2output 你看下楼主回复我的，不是因为相等，是因为 a 小于一亿，b 大于一亿这种情况没算。

[litmxs]

10s, 500Mb 内存
C++多线程, 上古 i5 笔记本
和昨天一样的思路写的, 参照这篇文章进行了优化: https://www.xarg.org/puzzle/project-euler/problem-21/
答案是 462 个(入伙可以相等的话那就是 467 个
优化空间还很大, 应该还可以优化到 5s 内
https://gist.github.com/LiTianxiong/40263593e9464a205e567b4cf1d4314b

[ksedz]

$ time ./main
467

real 0m7.801s
user 0m7.579s
sys 0m0.228s

先算出 1 亿以内所有质数，然后对幂次做深搜，占内存有点大，2G 多

https://gist.github.com/shapled/e21a6d5ecd8129a6a7bccc84d1f67b9a

[123444a]

分解素因子即可，很多年前的题目了

[liyunlong41]

@Ultraman 应该是意识到算法的差距吧

[liyunlong41]

应该是有相应的算法来求解的，但是我不会~，直接暴力求的…，1 亿以内 462 个，golang，19 秒，790M 内存。
func TestDn(t *testing.T) {
const N = 1e8
var dn = make([]int, N+1)
for i := 2; i+i <= N; i++ {
for j := i << 1; j <= N; j += i {
//fmt.Println(j)
dn[j] += i
}
}
count := 0
for a := 2; a <= N; a++ {
b := dn[a] + 1
if b != a {
if b <= N && dn[b]+1 == a {
//fmt.Println(a, b)
count++
}
}
}
fmt.Println("count:", count)
}

[123444a]

@liyunlong41 这是 acm 题，19s 通不过的

[liyunlong41]

@123444a 思想交流而已，不用这么认真。再说能跑出数据来了，打表不随便过嘛。

[123444a]

@liyunlong41 没人告诉你止于 1 亿哦

[123444a]

最终就是要打表滴呵呵