一些Rust基础数学算法

因数/质因数算法

找出n的因数

fn factor(n: usize) -> Vec<usize> {
    (1..).take_while(|i| i * i <= n)
        .filter(|x| n%x ==0)
        .collect::<Vec<usize>>()
}

fn factor_full(n: usize) -> Vec<(usize,usize)> {
    (1..).take_while(|i| i * i <= n)
        .filter(|x| n%x ==0)
        .map(|x| (x, n/x))
        .collect::<Vec<(usize,usize)>>()
}

求n的质因数序列

fn factor_primes(n: usize) -> Vec<usize> {
    let mut a = 2;
    let mut m = n;
    let mut result = Vec::new();
    for i in a..=m {
        while n != i {
            if m % i == 0 {
                let t: usize = *result.last().unwrap_or(&0);
                if t != i {
                    result.push(i);
                }
                m = m / i
            } else {
                break;
            }
        }
    }
		if result.len() == 0 {
        return vec![1,n];
    }

    result
}

分解质因数 算法同上

fn factor_primes(n: usize) -> Vec<usize> {
    let mut a = 2;
    let mut m = n;
    let mut result = Vec::new();
    for i in a..=m {
        while n != i {
            if m % i == 0 {
                result.push(i);
                m = m / i
            } else {
                break;
            }
        }
    }
    
    if result.len() == 0 {
        return vec![1,n];
    }

    result
}

参考链接

质因数分解及代码： - youxin - 博客园

就是一个数的 约数，并且是 质数，比如8=2×2×2，2就是8的质因数。12=2×2×3，2和3就是12的质因数。把一个式子以12=2×2×3的形式表示，叫做 分解质因数。16=2×2×2×2,2就是16的质因数，。[1] 分解质因数的方法是先用一个合数的最小质因数去除这个合数，得出的数若是一个质数，就写成这个合数相乘形式；若是一个合数就继续按原来的方法，直至最后是一个质数 。 ...

https://www.cnblogs.com/youxin/p/3232049.html

素数算法

找出n内的素数

use std::collections::HashMap;

fn find_primes(n: usize) -> Vec<usize> {
    let mut result = Vec::new();
    let mut is_prime = HashMap::new();
    is_prime.insert(2, true);
    is_prime.insert(3, true);
    is_prime.insert(5, true);
    is_prime.insert(7, true);

    for i in 2..=n {
        let is_pr = is_prime.entry(i).or_insert(true);
        if *is_pr {
            result.push(i);
        }

        ((i * 2)..=n).step_by(i).for_each(|x| {
            is_prime.entry(x).or_insert(false);
        });
    }

    result
}

vec版本, 实测速度更快, 空间略大

fn find_primes(n: usize) -> Vec<usize> {
    let mut result = Vec::new();
    let mut is_prime = vec![true; n + 1];

    for i in 2..=n {
        if is_prime[i] {
            result.push(i);
        }

        ((i * 2)..=n).step_by(i).for_each(|x| {
            is_prime[x] = false;
        });
    }

    result
}

参考链接

一次找出范围内的所有素数，埃式筛法是什么神仙算法？

本文始发于个人公众号： TechFlow，原创不易，求个关注 今天这篇是 算法与数据结构 专题的第23篇文章，我们继续数论相关的算法，来看看大名鼎鼎的埃式筛法。 我们都知道在数学领域，素数非常重要，有海量的公式和研究关于素数，比如那个非常著名至今没有人解出来的哥德巴赫猜想。和数学领域一样，素数在信息领域也非常重要，有着大量的应用。举个简单的例子，很多安全 加密算法 ...

https://zhuanlan.zhihu.com/p/146418699

线性筛选法

fn find_primes(n: usize) -> Vec<usize> {
    let mut result = vec![0; n + 1];
    let mut is_prime = vec![true; n + 1];
    let mut count = 0;
    for i in 2..=n {
        if is_prime[i] {
            result[count] = i;
            count += 1;
        }

        let mut j = 0;
        while result[j] * i <= n {
            is_prime[result[j] * i] = false;
            if (i % result[j]) == 0 {
                break;
            }
            j += 1;
        }
    }

    result.retain(|x| *x != 0);
    result
}

参考链接

197. 阶乘分解 (质因数)

思路： 很明显这题直接采用大数运算是不行的，所以我们来研究一下 n 的阶乘的结果中质因子的特点。 神奇的数学原理： 15/4 下取整为3，这就意味着在[1,15] 区间内的整数中 是4的倍数的数有3 个。(不信你试试 ( 逃~ 题解： 线性筛出1~n内的质数，因为n 的阶乘的结果质因数分解后，这些质数都会出现 (应该能理解吧) ，但是我们不知道出现了多少次，也就是不知道这个质因子是多少次方，所以我们利用上边的数学原理统计这个质因子出现了多少次。 举个样例中的 例子 ：在5的阶乘中，找2的次方数，那么我们先用5/2 得 2，那就是说2的倍数的数有2个 分别是 2和4，然后我们再5 / (2*2) 得1，那就是说4的倍数有1个，那就是4，这样一来，4被统计了两次，2被统计了一次，所以2的次方数是3。🆗结束 代码：

https://blog.csdn.net/weixin_44851176/article/details/105010470

其它算法

判断n是否为完全平方数

fn is_perfect_square(num:usize) ->bool {
    let mut x = num;
    while (x * x) > num {
        x = (x + num / x)/2;
    }
    return x * x == num;
}

参考链接

Leetcode 367: Valid Perfect Square

给你一个正整数num，写一个函数来判断如果num是完全平方数，则返回True，反之则返回False。 注意: 不要使用任何的内置函数比如 sqrt 。 例子1： 输入: 16返回: True 例子2： 输入: 14输出: False 这个题目很简单，就是判断一下一个数是否是完全平方数。 我最开始的思路是，从1开始到num，依次判断每个数的平方是否等于num，若大于num，则直接退出返回False。但是这样会存在溢出的情况，且运算速度较慢。 我们可以采用二分法来改善时间复杂度。同时我们可以找出在int范围内的最大的平方根，为46340。然后我们再来进行判断。具体代码如下： 下面我们来介绍第二种方法，首先我们来看一个数列，1，3， 5，7...2n -1。根据等差数列求和我们可以得到这个数列的和为 。所以我们可以得出一个完全平方数可以写成1+3+5+7... 根据上面的结论，我们可以让num一直减奇数数列，看最后是否为0。具体如下： 除了上面的两种方法，我们还可以使用 牛顿法，具体牛顿法，大家可以去看一些博客或者看wiki，主要就是切线逼近的思想，将 转化为 的方式来求解，利用切线一直逼近方程的解。 具体代码如下： 这个题目比较简单，但是方法较多，涉及一些数论知识和数学方法，所以关于常见的一些数学知识和结论要掌握，这样遇到题目，就可以很快的做出来。 欢迎大家交流，点赞的人运气都不会差~~

https://zhuanlan.zhihu.com/p/33378294

最大公约数 & 最小公倍数

fn gcd(a: i64, b: i64) -> i64 { if b == 0 { a } else { gcd(b, a % b)} }
fn lcm(a: i64, b: i64) -> i64 { a / gcd(a, b) * b }