试除法

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. }