先说最暴力的算法,直接对一万内的每个数字暴力分解因子(对每个数字的时间复杂度是O(sqrt(n)的),然后,用个数组记录下来因子和,然后寻找 亲密数。
好一点:要先打个素数表,然后对每个数字,分解素因子, 假设因子和函数为,则, 推导后: ------>证明过程见《初等数论及其应用》(原书第六版)184-185页 有个坑就是a!=b,在这里错了好几发。。。。 看了下官方的题解,最终用的方法就是我图片里的那个公式。 ------------->开启了支持数学公式,可是还是不支持,很蛋疼,所以传了图片