素因数分解機

main.rs

// Written on: 2022/02/20

use std::io;
use num_bigint::BigUint;

fn main() {
    println!("Type a number:");
    let number = read();
    let factors = factorize(number.clone());

    println!("{} = {:?}", number, factors);
}

fn read() -> BigUint {
    let mut input = String::new();
    io::stdin().read_line(&mut input).ok();
    input.trim().parse().unwrap_or(BigUint::from(0_u8))
}

fn factorize(n: BigUint) -> Vec<u32> {
    if n < BigUint::from(3_u8) {
        return vec![n.to_u32_digits()[0]];
    }
    let mut number = n;

    let mut current: u32 = 3;
    let mut primes: Vec<u32> = vec![2];
    let mut output: Vec<u32> = vec![];

    while &number % 2_u8 == BigUint::from(0_u8) {
        output.push(2);
        number /= 2_u8;
    }

    loop {
        let mut is_prime = true;
        for p in &primes {
            if current % p == 0 {
                is_prime = false;
                break;
            }
        }
        if is_prime {
            primes.push(current);
            while &number % current == BigUint::from(0_u8) {
                output.push(current);
                number /= current;
            }
            if number == BigUint::from(1_u8) {
                break;
            }
        }
        current += 2;
    }
    output
}