试除法

  1. fn floor(value: f64, scale: u8) -> f64 {
  2.     let multiplier = 10i64.pow(scale as u32) as f64;
  3.     (value * multiplier).floor()
  4. }
  6. fn double_to_int(amount: f64) -> i128 {
  7.     amount.round() as i128
  8. }
  10. pub fn trial_division(mut num: i128) -> Vec<i128> {
  11.     let mut result: Vec<i128> = vec![];
  13.     while num % 2 == 0 {
  14.         result.push(2);
  15.         num /= 2;
  16.         num = double_to_int(floor(num as f64, 0))
  17.     }
  18.     let mut f: i128 = 3;
  20.     while f.pow(2) <= num {
  21.         if num % f == 0 {
  22.             result.push(f);
  23.             num /= f;
  24.             num = double_to_int(floor(num as f64, 0))
  25.         } else {
  26.             f += 2
  27.         }
  28.     }
  30.     if num != 1 {
  31.         result.push(num)
  32.     }
  33.     result
  34. }
  36. #[cfg(test)]
  37. mod tests {
  38.     use super::*;
  40.     #[test]
  41.     fn basic() {
  42.         assert_eq!(trial_division(9), vec!(3, 3));
  43.         assert_eq!(trial_division(10), vec!(2, 5));
  44.         assert_eq!(trial_division(11), vec!(11));
  45.         assert_eq!(trial_division(33), vec!(3, 11));
  46.         assert_eq!(trial_division(2003), vec!(2003));
  47.         assert_eq!(trial_division(100001), vec!(11, 9091));
  48.     }
  49. }