11: Add solution for Rust track exercise "Nth Prime".

[?]

Aaw9nJhsNmfzFih9mKyNw9mV8CgERXJkRa1kK1Kx3LQH

Aug 17, 2021, 1:30 AM

ERYD4CD76UGRWQJXSVEPME4XJNQOGECALQEB3NBE76RLJX22TX6AC

Dependencies

[2] JZN2AQ3E 10: Add Rust track exercise "nth-prime".

Change contents

replacement in rust/nth-prime/tests/nth-prime.rs at line 5

[2.132]→[2.132:163](∅→∅)

assert_eq!(np::nth(0), 2);

[2.132]

[2.163]

assert_eq!(np::nth(0), 2);
replacement in rust/nth-prime/tests/nth-prime.rs at line 11

[2.209]→[2.209:240](∅→∅)

assert_eq!(np::nth(1), 3);

[2.209]

[2.240]

assert_eq!(np::nth(1), 3);
replacement in rust/nth-prime/tests/nth-prime.rs at line 17

[2.285]→[2.285:317](∅→∅)

assert_eq!(np::nth(5), 13);

[2.285]

[2.317]

assert_eq!(np::nth(5), 13);
replacement in rust/nth-prime/tests/nth-prime.rs at line 23

[2.360]→[2.360:402](∅→∅)

assert_eq!(np::nth(10_000), 104_743);

[2.360]

[2.402]

assert_eq!(np::nth(10_000), 104_743);
edit in rust/nth-prime/src/lib.rs at line 1

[2.452]

[2.453]

/*
Uses Sieve of Eratosthenes with some optimisations:
* Approximates size of the list required using the inverse of an approximation of the prime-counting function to save allocating too much extra space.
* Marks multiples starting from square of current prime.
* Stops marking multiples when the current index is ceil(sqrt(list size)) as the prime before that will be the last prime we need to check multiples for.
*/
replacement in rust/nth-prime/src/lib.rs at line 8

[2.481]→[2.481:547](∅→∅)

unimplemented!("What is the 0-indexed {}th prime number?", n)

[2.481]

[2.547]

// List size approximation is insufficient for values of n = 0, 1, 2, 3, 4, 5, 6, 9 and 11, with the greatest difference of 4 when n = 2, requiring this correction.
let corrected_n = if n > 11 { n as f64 } else { (n + 4) as f64 };
// Approximated size of the list required using the inverse of an approximation of the prime-counting function.
let list_size = (corrected_n * (corrected_n * corrected_n.ln()).ln()).ceil() as usize;
/*
Index at which we can stop marking new multiples.
Array representing list of numbers.
Prime count.
*/
let (limit, mut list, mut count) = (
(list_size as f64).sqrt() as usize + 1,
vec![true; list_size],
0,
);

for index in 2..list_size {
if list[index] {
count += 1;
if count > n {
// Might return incorrect value if values greater than u32::MAX are cast.
return index as u32;
}
if index < limit {
for multiple in (index * index..list_size).step_by(index) {
list[multiple] = false;
}
}
}
}

unreachable!();