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. 开始你的表演
3. 测试代码查看
#![allow(unused_variables)]
fn main() {
#[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. 答案
#![allow(unused_variables)]
fn main() {
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
}
}