SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 66 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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top