通过欧拉计划学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电子书。
