# 通过欧拉计划学Rust编程（第69题）

“欧拉计划”的网址： https://projecteuler.net

https://projecteuler.net/problem=69

n

φ(n)

n/φ(n)

2

1

1

2

3

1, 2

2

1.5

4

1, 3

2

2

5

1, 2, 3, 4

4

1.25

6

1, 5

2

3

7

1, 2, 3, 4, 5, 6

6

1.1666…

8

1, 3, 5, 7

4

2

9

1, 2, 4, 5, 7, 8

6

1.5

10

1, 3, 7, 9

4

2.5

```fn main() {
let mut max_ratio = 0_f64;
for n in 2..=1_000_000 {
// 最大公约数为1，表示互质
let phi = (1..n).filter(|&x| gcd(x, n) == 1).count();
let ratio = (n as f64) / (phi as f64);
if ratio > max_ratio {
println!("n= {:6}  phi={:6}  n/phi= {:.4}", n, phi, ratio);
max_ratio = ratio;
}
}
}

// 最大公约数
fn gcd(a: u64, b: u64) -> u64 {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
```

```n=      2  phi=     1  n/phi= 2.0000
n=      6  phi=     2  n/phi= 3.0000
n=     30  phi=     8  n/phi= 3.7500
n=    210  phi=    48  n/phi= 4.3750
n=   2310  phi=   480  n/phi= 4.8125
n=  30030  phi=  5760  n/phi= 5.2135
```

```// 2 * 3 * 5 * 7 * 11 * ... 找到最多的素数，乘积在1百万以内
let mut pset = PrimeSet::new();
let mut prod = 1;
for p in pset.iter() {
if prod * p > 1_000_000 {
break;
}
prod *= p;
println!("prime={} {}", p, prod);
}
println!("{}", prod);
```

```let mut some_primes = (2..).filter(|&x| primes::is_prime(x));
let mut prod = 1;
let some_products = std::iter::repeat_with(|| {
let tmp = prod;
prod *= some_primes.next().unwrap();
tmp}).take_while(|&x| x <= 1_000_000)
.collect::<Vec<_>>();
println!("{:?}", some_products);
println!("{:?}", some_products.last().unwrap());
```

```let mut some_primes = (2..).filter(|&x| primes::is_prime(x));
let result = itertools::iterate(1, |&prod| prod * some_primes.next().unwrap())
.take_while(|&x| x <= 1_000_000)
.last()
.unwrap();
println!("{:?}", result);
```

```let mut max_ratio = 0_f64;
for n in 2..=1_000_000 {
let all_factors = primes::factors(n);
let uniq_factors = primes::factors_uniq(n);

let mut phi = 1;
for p in uniq_factors {
let k = all_factors.iter().filter(|&x| *x == p).count();
phi *= p.pow(k as u32 - 1) * (p-1);
}
let ratio = (n as f64) / (phi as f64);
if ratio > max_ratio {
println!("n= {:6}  phi={:6}  n/phi= {:.4}", n, phi, ratio);
max_ratio = ratio;
}
}
```

```let mut max_ratio = 0_f64;
for n in 2..=1_000_000 {
let uniq_factors = primes::factors_uniq(n);
let mut phi = n;
for p in uniq_factors {
phi = phi * (p-1) / p;
}
let ratio = (n as f64) / (phi as f64);
if ratio > max_ratio {
println!("n= {:6}  phi={:6}  n/phi= {:.4}", n, phi, ratio);
max_ratio = ratio;
}
}
```

--- END ---

0 条评论

• ### 搞定GTD - 项目分类

GTD中管理的是一堆Action，比如我的OmniFocus中当前有695个Action，包括已完成的、暂停的和未完成的。为了有效地管理这些Action，在GT...

• ### 用欧拉计划学Rust编程(第35~38题)

最近想学习Libra数字货币的MOVE语言，发现它是用Rust编写的，所以先补一下Rust的基础知识。学习了一段时间，发现Rust的学习曲线非常陡峭，不过仍有快...

• ### 通过欧拉计划学习Rust编程(第17~21题)

最近想学习Libra数字货币的MOVE语言，发现它是用Rust编写的，所以先补一下Rust的基础知识。学习了一段时间，发现Rust的学习曲线非常陡峭，不过仍有快...

• ### 人人都可以做深度学习应用：入门篇（上）

如果这一轮AI浪潮真的会带来新的一轮科技革命，那么我们相信，它也会遵循类似的发展轨迹，逐步发展和走向普及。如果基于这个理解，或许，我们可以通过积极学习，争取成为...

• ### [LeetCode] 129. Sum Root to Leaf Numbers

【原题】 Given a binary tree containing digits from 0-9 only, each root-to-leaf pa...

• ### Android Animations动画使用详解

Android的animation由四种类型组成：alpha、scale、translate、rotate

• ### Codechef Chef and Easy Problem(智商)

You are given a sequence A1, A2, ..., AN and Q queries. In each query, you are g...

• ### 04:错误探测

04:错误探测 总时间限制: 1000ms 内存限制: 65536kB描述 给定n*n由0和1组成的矩阵，如果矩阵的每一行和每一列的1的数量都是偶数，则认为...

• ### 洛谷P2870 [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold

题目描述 FJ is about to take his N (1 ≤ N ≤ 30,000) cows to the annual"Farmer of the...

• ### 亲测好用，AI论文写作工具推荐

【导语】今天这篇文章，主要为大家介绍了在AI领域论文写作中几个好用的工具，总结的这些工具都是作者自己在写作过程中用的比较顺手的工具，看看是不是你也在用？如果有其...