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

[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
• 昨天的题，欢迎继续讨论

[nomoon]

楼主你这是在刷 project euler 么？

[YUX]

@nomoon #41 嗯

[wutiantong]

我不能认同把这个叫做数学题，作为算法题这也挺无趣的。

[starqoq]

首先用线性素数筛把所有素数都找出来，对于合数，也可以记录一个因子。
然后对于和数 d(X) = d(X/p) + p (p 是 X 的一个因子)

然后在扫一下满足 d(X)!=X && d(d(X))=X 即可
复杂度 O(n)

[macg0406]

先求 X 的所有因子之和，可以用递推方式求解，f(k) = f(m) * f(n), 如果 k = m * n，并且 m, n 互质。然后减去本身就得到了本题中的 d(x)。

time ./a.out
462
./a.out 4.06s user 0.14s system 99% cpu 4.202 total

时间复杂度不超过 O(n logn)空间复杂度是 O(n)

[macg0406]

@macg0406 贴 github 链接需要手机认证。。。
链接 base64: aHR0cHM6Ly9naXN0LmdpdGh1Yi5jb20vbWFjZzA0MDYvOGE1MzU0M2U0ZTQxNjkyZjEyMjYxMjEyM2Y2ZWNhZjc=