第23题-非丰富数和

本文包含欧拉项目第23题的解法

问题描述

第23题图

这个问题翻译为中文就是：

如果一个数等于它的因数之和，那这个数就叫完美数，如28=1+2+4+7+14，如果它的因数之和小于这个数，那这个数叫做匮乏数，反之如果因数之和大于这个数，则成为丰富数

12是最小的丰富数，12 < 1+2+3+4+6，24是能被表示为2个丰富数之和的数中最小的那个，通过数学分析，所有比28123大的数都可以写成2个丰富数之和

求解：找到所有的不可以表示为2个丰富数之和的数，返回它们的和

解题思路

这题关键是要读懂题意，超过28123的数都不符合条件，所以可能的数必然在[1, 28123]之间，按理来说这是一个很小的区间，不管用什么算法肯定都很快算出答案

今天上班摸鱼的时候做的这题，一开始以为很简单暴力可破，但是后来发现程序如果不经优化可以很慢，我经历了运行时间由10分钟到30秒到低于1s的过程，挺有意思的

rust语言实现

p23.rs

pub fn solution() -> usize {
    let mut abundant_arr = vec![];
    let threshold = 28123;
    for i in 12..=threshold {
        if is_abundant(i) {
            abundant_arr.push(i);
        }
    }
    let abundant_arr_len = abundant_arr.len();
    let mut target_arr: Vec<usize> = (0..=threshold).collect(); // 优化点1
    for i in 0..abundant_arr_len {
        for j in i..abundant_arr_len { // 优化点4
            let s = abundant_arr[i] + abundant_arr[j];
            if s <= threshold {
                target_arr[s] = 0; // 优化点2
            }
        }
    }
    return target_arr.iter().sum();
}

fn is_abundant(num: usize) -> bool {
    let mut divisor_sum = 1;
    let mid = (num as f64).sqrt() as usize + 1; // 优化点3
    for i in 2..mid+1 {
        if num % i == 0 {
            let q = num / i;
            if i < q {
                divisor_sum += i;
                divisor_sum += q;
            }
            if i == q {
                divisor_sum += i;
            }
        }
    }
    if divisor_sum > num {
        return true;
    }
    return false;
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_is_abundant() {
        for i in 1..12 {
            assert_eq!(false, is_abundant(i));
        }
        assert_eq!(true, is_abundant(12));
        assert_eq!(false, is_abundant(13));
        assert_eq!(false, is_abundant(16));
        assert_eq!(true, is_abundant(4088));
        assert_eq!(true, is_abundant(20));
        assert_eq!(false, is_abundant(28)); // 28 is perfect number, so not abundant number
    }

    #[test]
    fn test_solution() {
        assert_eq!(4179871, solution());
    }
}

代码解释

基本思路是先把[12, 28123]之间的丰富数都提取出来存放到一个数组中，大概有6000多个这样的数，遍历2遍这个数组，找出能表示为2个丰富数之和的数剔除出来，剩下的就是不能被表示的，然后求和就行了。代码后面按照惯例包含单测和功能测试

有几个优化点需要注意：

1. 通过迭代器快速生成数组，性能远远好于循环插入

2. 剔除元素时直接把数组对应位置标记为0，性能远远好于remove或者find之后删除等方法，数组直接读写是常数时间，而查找最快也要 $O(nlgn)$
3. 算一个数的所有因数时，不需要遍历这个数以内的所有数，到平方根处就行，能很大的减少不必要的计算量

4. 两次遍历数组时，j从i处开始就行，避免重复计算，而且i、j是可以相等的

做完之后发现论坛上很多大神分享了各种稀奇古怪的解法，有兴趣的小伙伴可以去参考下