28 lines
723 B
Rust
28 lines
723 B
Rust
use num::integer::gcd;
|
|
|
|
fn main() {
|
|
// Compute the totient of the first 25 natural integers
|
|
println!("N\t phi(n)\t Prime");
|
|
for n in 1..26 {
|
|
let phi_n = phi(n);
|
|
println!("{}\t {}\t {:?}", n, phi_n, phi_n == n - 1);
|
|
}
|
|
|
|
// Compute the number of prime numbers for various steps
|
|
[1, 100, 1000, 10000, 100000]
|
|
.windows(2)
|
|
.scan(0, |acc, tuple| {
|
|
*acc += (tuple[0]..=tuple[1]).filter(is_prime).count();
|
|
Some((tuple[1], *acc))
|
|
})
|
|
.for_each(|x| println!("Until {}: {} prime numbers", x.0, x.1));
|
|
}
|
|
|
|
fn is_prime(n: &usize) -> bool {
|
|
phi(*n) == *n - 1
|
|
}
|
|
|
|
fn phi(n: usize) -> usize {
|
|
(1..=n).filter(|&x| gcd(n, x) == 1).count()
|
|
}
|