• API
• FAQ
• Tools
• Archive
daily pastebin goal
20%
SHARE
TWEET

# Untitled

a guest Mar 23rd, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. use std::iter;
2.
3. fn optimized_sieve(limit: usize) -> impl Iterator<Item = usize> {
4.     let map_func = |cmpsts: Vec<u32>| {
5.         move |i| {
6.             if i < 0 {
7.                 Some(2)
8.             } else {
9.                 if cmpsts[i as usize >> 5] & (1u32 << (i & 31)) == 0 {
10.                     Some((i + i + 3) as usize)
11.                 } else {
12.                     None
13.                 }
14.             }
15.         }
16.     };
17.
18.     // Weird-looking exprs so types line up
19.     if limit == 2 {
20.         return (0..0).into_iter().filter_map(map_func(vec![]));
21.     } else if limit < 2 {
22.         return (-1..0).into_iter().filter_map(map_func(vec![]));
23.     }
24.
25.     let ndxlmt = (limit - 3) / 2 + 1;
26.     let bfsz = ((limit - 3) / 2) / 32 + 1;
27.     let mut cmpsts = vec![0u32; bfsz];
28.     let sqrtndxlmt = ((limit as f64).sqrt() as usize - 3) / 2 + 1;
29.
30.     for ndx in 0..sqrtndxlmt {
31.         if (cmpsts[ndx >> 5] & (1u32 << (ndx & 31))) == 0 {
32.             let p = ndx + ndx + 3;
33.             let mut cullpos = (p * p - 3) / 2;
34.             while cullpos < ndxlmt {
35.                 cmpsts[cullpos >> 5] |= 1u32 << (cullpos & 31);
36.                 cullpos += p;
37.             }
38.         }
39.     }
40.
41.     (-1..ndxlmt as isize)
42.         .into_iter()
43.         .filter_map(map_func(cmpsts))
44. }
45.
46. fn nth_prime_upper_bound(n: usize) -> Option<usize> {
47.     if let Some(upper) = [0, 2, 3, 5, 7, 11].get(n) {
48.         return Some(*upper);
49.     }
50.
51.     let n_f64 = n as f64;
52.     let logn = n_f64.log2();
53.     let loglogn = logn.log2();
54.
55.     let upper = match n {
56.         n if n >= 688383 => n_f64 * (logn + loglogn - 1. + ((loglogn - 2.) / logn)),
57.         n if n >= 178974 => n_f64 * (logn + loglogn - 1. + ((loglogn - 1.95) / logn)),
58.         n if n >= 39017 => n_f64 * (logn + loglogn - 1. + ((loglogn - 0.9484) / logn)),
59.         _ => n_f64 * (logn + 0.6 * loglogn),
60.     };
61.
62.     let upper = upper.ceil();
63.
64.     if upper <= std::usize::MAX as f64 {
65.         Some(upper as _)
66.     } else {
67.         None
68.     }
69. }
70.
71. #[no_mangle]
72. pub extern "C" fn nth_prime(n: usize) -> usize {
73.     optimized_sieve(nth_prime_upper_bound(n).expect("Bound on nth prime exceeds usize"))
74.         .nth(n)
75.         .expect("nth prime was not in bounds")
76. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top