Prime Factors

1. Readme

素数因子

计算给定自然数的素因子.

质数(素数): 只能被自身和 1 整除.

注意,1 不是素数.

例子

60 的主要因素是什么?

  • 我们的第一个除数是 2 。 2 被除以 60,剩下 30。
  • 2 被除以 30,剩下 15。
    • 2 不能被除以 15。让我们转到下一个除数,3.
  • 3 被除以 15 分,5 剩下。
    • 3 不能被除以 5。下一个可能的因素是 4.
    • 4 不能被除以 5。下一个可能的因素是 5.
  • 5 确实能被除以 5.
  • 我们只剩下 1 ,所以现在,我们完成了。

我们在该计算中成功, 而 60除数代表 ∶ 2, 2, 3 和 5 为主要因子的列表.

你可以自己检查一下:

  • 2 × 2 × 3 × 5
  • = 4 × 15
  • = 60
  • 成功!

资源

Uncle Bob 的主要因素算法http://butunclebob.com/ArticleS.UncleBob.ThePrimeFactorsKata

2. 开始你的表演

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

3. 测试代码查看

#[test] fn test_no_factors() { assert_eq!(factors(1), vec![]); } #[test] //#[ignore] fn test_prime_number() { assert_eq!(factors(2), vec![2]); } #[test] //#[ignore] fn test_square_of_a_prime() { assert_eq!(factors(9), vec![3, 3]); } #[test] //#[ignore] fn test_cube_of_a_prime() { assert_eq!(factors(8), vec![2, 2, 2]); } #[test] //#[ignore] fn test_product_of_primes_and_non_primes() { assert_eq!(factors(12), vec![2, 2, 3]); } #[test] //#[ignore] fn test_product_of_primes() { assert_eq!(factors(901255), vec![5, 17, 23, 461]); } #[test] //#[ignore] fn test_factors_include_large_prime() { assert_eq!(factors(93819012551), vec![11, 9539, 894119]); }

4. 答案

pub fn factors(n: u64) -> Vec<u64> { let mut val = n; let mut out: Vec<u64> = vec![]; let mut possible: u64 = 2; while val > 1 { while val % possible == 0 { out.push(possible); val /= possible; } possible += 1; } out }



填充/相关