wmathrs 0.1.0

/// 判断x是不是素数
pub fn is_prime(x: u128) -> bool {
    if (x <= 2) || (x % 2 == 0) {
        return false; 
    }
    let mut _is_prime = true; 
    let sqrt = (x as f64).sqrt() as u128; 
    let mut i = 3; 
    while i <= sqrt {
        if x % i == 0 {
            _is_prime = false; 
            break; 
        }
        i += 2; 
    }
    return _is_prime; 
}

/// 找出所有不大于x的素数
pub fn find_prime_until(x: u128) -> Vec<u128> {
    if x < 2 { return vec![]; }
    let mut prime = vec![2u128]; 
    let mut i  = 3; 
    let mut is_prime; 
    let mut sqrt; 
    while i <= x {
        is_prime = true; 
        sqrt = (i as f64).sqrt() as u128; 
        for j in 0..prime.len() {
            if prime[j] > sqrt { break; }
            if i % prime[j] == 0 {
                is_prime = false; 
                break; 
            }
        }
        if is_prime { prime.push(i); }
        i += 2; 
    }
    return prime; 
}

/// 找出x的所有素因子
pub fn prime_factor_without_exp(x: u128) -> Vec<u128> {
    let mut _x = x; 
    if _x < 2 { return vec![]; }
    let mut sqrt = (_x as f64).sqrt() as u128; 
    let mut vec = vec![]; 
    let mut i = 2; 
    while i <= sqrt {
        if _x % i == 0 {
            vec.push(i); 
            while _x % i == 0 { _x /= i; }
            sqrt = (_x as f64).sqrt() as u128; 
        }
        if _x == 1 { break; }
        i += 1; 
    }
    if _x != 1 { vec.push(_x); }
    return vec; 
}

use std::collections::HashMap; 
/// 找出x的所有素因子和对应的次数
pub fn prime_factor_with_exp(x: u128) -> HashMap<u128, u128> {
    let mut _x = x; 
    let mut map = HashMap::new(); 
    if _x < 2 { return map; }
    let mut sqrt = (_x as f64).sqrt() as u128; 
    let mut i = 2; 
    while i <= sqrt {
        if _x % i == 0 {
            let mut count = 0; 
            while _x % i == 0 { 
                _x /= i; 
                count += 1; 
            }
            map.insert(i, count); 
            sqrt = (_x as f64).sqrt() as u128; 
        }
        if _x == 1 { break; }
        i += 1; 
    }
    if _x != 1 { map.insert(_x, 1); }
    return map; 
}

/// 找出x的所有正因数
pub fn factor(x: u128) -> Vec<u128> {
    if x == 0 { return vec![]; }
    if x == 1 { return vec![1u128]; }
    fn vector_multiple(a: &Vec<u128>, b: &Vec<u128>) -> Vec<u128> {
        let mut vec = vec![]; 
        for i in a.iter() {
            for j in b.iter() {
                vec.push(i * j); 
            }
        }
        return vec; 
    }
    let _prime_factor_with_exp = prime_factor_with_exp(x); 
    let mut vec2d = vec![]; 
    for (prime, exp) in _prime_factor_with_exp {
        let mut vec = vec![1u128]; 
        let mut _prime = prime; 
        for _i in 1..=exp {
            vec.push(_prime); 
            _prime *= prime; 
        }
        vec2d.push(vec); 
    }
    let mut len = vec2d.len(); 
    while len != 1 {
        vec2d[len - 2] = vector_multiple(&vec2d[len - 2], &vec2d[len - 1]); 
        vec2d.pop(); 
        len = vec2d.len(); 
    }
    return vec2d[0].to_owned(); 
}

/// 求两个数的最大公约数
pub fn greatest_common_divisor(a: u128, b: u128) -> u128 {
    if b == 0 { return a; }
    let mut _a = a; 
    let mut _b = b; 
    while _a % _b != 0 {
        let mid = _b; 
        _b = _a % _b; 
        _a = mid; 
    }
    return _b; 
}

/// 求一组数的最大公约数
pub fn greatest_common_divisor_in_vector(vec: &Vec<u128>) -> u128 {
    let mut gcd = vec[0]; 
    for value in vec {
        gcd = greatest_common_divisor(gcd, *value); 
        if gcd == 1 { break; }
    }
    return gcd; 
}

/// 求两个数的最小公倍数
pub fn leastest_common_multiple(a: u128, b: u128) -> u128 {
    if (a == 0) || (b == 0) { return 0u128; }
    return a * b / greatest_common_divisor(a, b); 
}

/// 求一组数的最小公倍数
pub fn leastest_common_multiple_in_vector(vec: &Vec<u128>) -> u128 {
    let mut lcm = vec[0]; 
    for value in vec {
        lcm = leastest_common_multiple(lcm, *value); 
        if lcm == 0 { break; }
    }
    return lcm; 
}

/// 返回(gcd, x, y)使得 a*x+b*y=gcd 成立
pub fn greatest_common_divisor_with_coefficient(a: u128, b: u128) -> (u128, i128, i128) {
    if b == 0 { return (a, 1i128, 0i128); }
    let (gcd, x, y) = greatest_common_divisor_with_coefficient(b, a % b); 
    let _x = y; 
    let _y = x - (a / b) as i128 * y; 
    return (gcd, _x, _y); 
}

/// 返回inv使得 a*inv = gcd(a,n) (mod n) 成立
pub fn inverse(a: u128, n: u128) -> u128 {
    let mut inv: i128 = greatest_common_divisor_with_coefficient(a, n).1 % n as i128; 
    if inv < 0 { inv += n as i128; }
    return inv as u128; 
}