SHARE
TWEET

Untitled

a guest Oct 21st, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. use std::ops::RangeInclusive;
  2.  
  3. fn main() {
  4.     max_root(2, 1000_000_000);
  5.     max_root(10, 20);
  6.     max_root(6000, 7000);
  7.     max_root(100_000_000, 100_000_000);
  8.     max_root(4, 16);
  9. }
  10.  
  11. fn max_root(from: u32, to: u32) -> u32 {
  12.     assert!(from >= 2);
  13.     assert!(to <= 1000_000_000);
  14.     assert!(from <= to);
  15.  
  16.     #[inline(always)]
  17.     fn dirty_root(x: u32) -> u32 {
  18.         f32::sqrt(x as f32) as u32
  19.     }
  20.  
  21.     fn rec(range: RangeInclusive<u32>, step: u32) -> Option<(u32, u32)> {
  22.         let (from, to) = range.clone().into_inner();
  23.         if to == 1 || from > to {
  24.             return None;
  25.         }
  26.  
  27.         let new_from = dirty_root(from);
  28.         let new_to = dirty_root(to);
  29.  
  30.         let contains_new_from = range.contains(&(new_from * new_from));
  31.         let contains_new_to = range.contains(&(new_to * new_to));
  32.  
  33.         let new_range = new_from.max(2)..=new_to;
  34.         let next_step = step + 1;
  35.  
  36.         if contains_new_from || contains_new_to {
  37.             match rec(new_range.clone(), next_step) {
  38.                 Some((num, the_step)) if range.contains(&(num * num)) => {
  39.                     Some((num * num, the_step))
  40.                 }
  41.                 _ => {
  42.                     if contains_new_from {
  43.                         Some((new_from * new_from, next_step))
  44.                     } else {
  45.                         Some((new_to * new_to, next_step))
  46.                     }
  47.                 }
  48.             }
  49.         } else {
  50.             None
  51.         }
  52.     }
  53.  
  54.     match rec(from..=to, 0) {
  55.         Some((num, step)) => {
  56.             println!("Number in charge [{}] on step [{}]", num, step);
  57.             step
  58.         }
  59.         None => 0,
  60.     }
  61. }
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