歐拉項目第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語言實現

pubfnsolution()-> usize {

letmut abundant_arr =vec![];

let threshold =28123;

for i in12..=threshold {

ifis_abundant(i){

abundant_arr.push(i);

}

}

let abundant_arr_len = abundant_arr.len();

letmut target_arr: Vec<usize>=(0..=threshold).collect();// 優化點1

for i in0..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();

}

fnis_abundant(num: usize)-> bool {

letmut divisor_sum =1;

let mid =(num as f64).sqrt()as usize +1;// 優化點3

for i in2..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 {

returntrue;

}

returnfalse;

}

#[cfg(test)]

mod tests {

usesuper::*;

#[test]

fntest_is_abundant(){

for i in1..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]

fntest_solution(){

assert_eq!(4179871,solution());

}

}

代碼解釋

基本思路是先把[12, 28123]之間的豐富數都提取出來存放到一個數組中，大概有6000多個這樣的數，遍歷2遍這個數組，找出能表示為2個豐富數之和的數剔除出來，剩下的就是不能被表示的，然後求和就行了。代碼後面按照慣例包含單測和功能測試

有幾個優化點需要注意：

1. 通過迭代器快速生成數組，性能遠遠好於循環插入

2. 剔除元素時直接把數組對應位置標記為0，性能遠遠好於remove或者find之後刪除等方法，數組直接讀寫是常數時間，而查找最快也要 O(nlgn)

3. 算一個數的所有因數時，不需要遍歷這個數以內的所有數，到平方根處就行，能很大的減少不必要的計算量

4. 兩次遍歷數組時，j從i處開始就行，避免重複計算，而且i、j是可以相等的

做完之後發現論壇上很多大神分享了各種稀奇古怪的解法，有興趣的小夥伴可以去參考下