SHARE
TWEET

Untitled

a guest Apr 18th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. extern crate bit_vec; // 0.4.4
  2. use bit_vec::BitVec;
  3.  
  4. fn main() {
  5.     println!("{:?}", backwards_prime(99999000, 100000000));
  6. }
  7.  
  8. fn backwards_prime(start: u64, stop: u64) -> Vec<u64> {
  9.     fn backwards(mut n: u64) -> u64 {
  10.         let mut r = 0;
  11.         while n > 0 {
  12.             r = r * 10 + n % 10;
  13.             n /= 10;
  14.         }
  15.         r
  16.     }
  17.  
  18.     let mut max = 100;
  19.     while max < stop {
  20.         max *= 10;
  21.     }
  22.     let (primes, sieve) = prime(max);
  23.  
  24.     let start = match primes.binary_search(&start) {
  25.         Ok(i) => i,
  26.         Err(i) => i,
  27.     };
  28.     let stop = match primes.binary_search(&stop) {
  29.         Ok(i) => i + 1,
  30.         Err(i) => i,
  31.     };
  32.  
  33.     primes
  34.         .iter()
  35.         .filter(|&p| {
  36.             let b = backwards(*p);
  37.             b != *p && sieve.get(b as usize).unwrap()
  38.         })
  39.         .cloned()
  40.         .collect()
  41. }
  42.  
  43. fn prime(max: u64) -> (Vec<u64>, BitVec) {
  44.     let mut primes = {
  45.         let max = max as f64;
  46.         let max = max / max.ln() * 1.1;
  47.         Vec::with_capacity(max as usize)
  48.     };
  49.  
  50.     let mut sieve = BitVec::from_elem(max as usize, true);
  51.     sieve.set(0, false);
  52.     sieve.set(1, false);
  53.  
  54.     for i in 2..max {
  55.         if sieve.get(i as usize).unwrap() {
  56.             primes.push(i)
  57.         }
  58.         for &p in primes.iter() {
  59.             if p * i >= max {
  60.                 break;
  61.             }
  62.             sieve.set((p * i) as usize, false);
  63.             if i % p == 0 {
  64.                 break;
  65.             }
  66.         }
  67.     }
  68.  
  69.     (primes, sieve)
  70. }
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
 
Top