通過歐拉計劃學Rust編程（第500題）
- 2020 年 3 月 14 日
- 筆記
由於研究Libra等數字貨幣編程技術的需要，學習了一段時間的Rust編程，一不小心刷題上癮。
「歐拉計劃」的網址： https://projecteuler.net
英文如果不過關，可以到中文翻譯的網站： http://pe-cn.github.io/
這個網站提供了幾百道由易到難的數學問題，你可以用任何辦法去解決它，當然主要還得靠編程，程式語言不限，論壇里已經有Java、C#、Python、Lisp、Haskell等各種解法，當然如果你直接用google搜索答案就沒任何樂趣了。
這次解答的是第500題：
https://projecteuler.net/problem=500
題目描述：
120的因子個數為16，事實上120是最小的有16個因子的數。
找出最小的有2^500500個因子的數，給出這個數除以500500507的餘數。
〓
〓
〓
〓
請
先
不
要
直
接
看
答
案
，
最
好
自
己
先
嘗
試
一
下
。
解題過程：
直接看最終的問題，2^500500是個天文數字，肯定不能用蠻力。遇到一個複雜的問題，可以先嘗試解決簡單的情況，然後慢慢逼近最終的問題。
第一步： 從簡單的情況入手找規律：
第650題里解決過因子個數的公式，還可以計算出所有因子之和。
fn min_number_has_factors(x: u64) -> u64 { for n in 2.. { let groups = factors_group(n); let factors_num = groups.iter().map(|(_, x)| x + 1).product::<u64>(); if factors_num == x { println!("{}, divisors num: {}", n, factors_num); print_factors_group(groups); return n; } } 0 } // 如果一個數有這些因子：[2, 2, 3, 3, 3, 3, 5, 7] // 則得到：[(2,2), (3,4), (5,1), (7,1)] fn factors_group(n: u64) -> Vec<(u64, u64)> { let factors = primes::factors(n); let groups = factors .iter() .group_by(|e| **e) .into_iter() .map(|(k, group)| (k, group.count() as u64)) .collect::<Vec<(u64, u64)>>(); groups } fn print_factors_group(groups: Vec<(u64, u64)>) { println!( "{}", &groups .iter() .map(|(k, v)| k.to_string() + &"^" + &v.to_string()) .join(" * ") ); println!( "divisors num: {}", &groups .iter() .map(|(_, v)| "(".to_string() + &v.to_string() + &"+1)") .join(" * ") ); }現在先嘗試計算幾個，慢慢尋找規律。
min_number_has_factors(4); // 2^2 min_number_has_factors(8); // 2^3 min_number_has_factors(16); // 2^4 min_number_has_factors(32); // 2^5 min_number_has_factors(64); // 2^6 min_number_has_factors(128); // 2^7 min_number_has_factors(256); // 2^8結果有：
6 = 2^1 * 3^1 因子個數 4= (1+1) * (1+1) 24 = 2^3 * 3^1 因子個數 8 = (3+1) * (1+1) 120 = 2^3 * 3^1 * 5^1 因子個數 16 = (3+1) * (1+1) * (1+1) 840 = 2^3 * 3^1 * 5^1 * 7^1 因子個數 32 = (3+1) * (1+1) * (1+1) * (1+1) 7560 = 2^3 * 3^3 * 5^1 * 7^1 因子個數 64 = (3+1) * (3+1) * (1+1) * (1+1) 83160 = 2^3 * 3^3 * 5^1 * 7^1 * 11^1 因子個數 128 = (3+1) * (3+1) * (1+1) * (1+1) * (1+1) 1081080 = 2^3 * 3^3 * 5^1 * 7^1 * 11^1 * 13^1 因子個數 256 = (3+1) * (3+1) * (1+1) * (1+1) * (1+1) * (1+1)第二步： 努力尋找規律
通過分析幾個簡單的特例，將一般性的公式推導出來，需要運用基礎的數學知識。
一個數n可以分解成如下形式，其中pi為素數因子。
那麼，它的因子個數為：
最終的因子個數可以表示為2 ^ 500500形式，令：
則有：
最終的結果要讓[b0, b1, b2…bi]的和為500500。現在來看一下這個數組是如何變化的，找出遞推的規律。
因子個數 2 = (2^1) [b0] = [1] 因子個數 4 = (2^1) * (2^1) [b0,b1] = [1,1] 因子個數 8 = (2^2) * (2^1) [b0,b1] = [2,1] 因子個數 16 = (2^2) * (2^1) * (2^1) [b0,b1,b2] = [2,1,1] 因子個數 32 = (2^2) * (2^1) * (2^1) * (2^1) [b0,b1,b2] = [2,2,1] 因子個數 64 = (2^2) * (2^2) * (2^1) * (2^1) [b0,b1,b2,b3] = [2,2,1,1] 因子個數 128 = (2^2) * (2^2) * (2^1) * (2^1) * (2^1) [b0,b1,b2,b3,b4] = [2,2,1,1,1] 因子個數 256 = (2^2) * (2^2) * (2^1) * (2^1) * (2^1) * (2^1) [b0,b1,b2,b3,b4,b5] = [2,2,1,1,1,1]這裡需要足夠的耐心，這個bi數組或者在末尾增加一個元素1，或者在前面的某個位置上數值增1。
如果其中的某一項增1，則數值增加：
如果尾部增加一項，數值增加：
上面的數值中，哪一項更小，則表示或者在尾部增加一個，或者原數組中的數值增1。
最後的程式碼：
fn p500(n: usize) -> u64 { let mut pset = PrimeSet::new(); let primes: Vec<_> = pset.iter().take(n).collect(); let primes_log: Vec<_> = primes.iter().map(|x| (*x as f64).log10()).collect(); let mut b = vec![1]; for _i in 2..=n { let mut min = primes_log[b.len()]; let mut pos = b.len(); // 默認尾部增加一個 for j in 0..b.len() { let temp = 2_f64.powf(b[j] as f64) * primes_log[j]; if temp < min { pos = j; min = temp; } if b[j] == 1 { break; // 後面的都不用判斷了 } } if pos == b.len() { b.push(1); } else { b[pos] += 1; } } let mut result = 1_u64; for i in 0..b.len() { let exp = 2_u32.pow(b[i]) - 1; for _j in 0..exp { result = result * primes[i] % 500500507; } } result }— END —
我把解決這些問題的過程記錄了下來，寫成了一本《用歐拉計劃學 Rust 編程》PDF電子書，請隨意下載。
鏈接：https://pan.baidu.com/s/1NRfTwAcUFH-QS8jMwo6pqw
提取碼：qfha
由於歐拉計劃不讓發布100題之外的解題步驟，否則封號，所以最新PDF不再公開，請加我微信（SLOFSLB）索要最新的PDF電子書。
