算法中常用到的数学知识：埃拉托色尼筛法(获取质数)、欧几里得算法(求两个数最大公因数)

不管是在项目中还是面试时，一定的算法能力都是极其重要的。大多数算法只要有一定的基础，给足够的时间是可以写出来的，然而有一类算法，说难也不难，说简单也不简单，这种算法通常涉及到某种数学知识，如果了解这种知识那写出来就是易如反掌，而没了解过相应知识的就只能使用暴力解法，数据稍微多一点就超时，甚至暴力都写不出来。本文就给大家讲解一下两种相关的数学知识。

1.埃拉托色尼筛法

适用场景：

        获取一段数字中所有的质数。

基本步骤：

        1.创建一个列表：首先，创建一个从2开始到你想要检查的数n（包括n）的连续整数列表。

        2.标记第一个数：从列表中的第一个数2开始，因为它是第一个质数。

        3.划除倍数：从2的下一个数开始，标记2的所有倍数。因为这些数都可以被2整除，所以它们不是质数。

        4.移动到下一个未标记的数：在列表中找到下一个未被划除的数，这个数就是下一个质数。对于这个新的质数，重复步骤3，划除它的所有倍数。

        5.重复步骤：继续这个过程，每次都找到下一个未被划除的数，并划除它的所有倍数，直到你处理完所有小于或等于√n的数。因为一个数必须有一个因数小于或等于它的算数平方根。

        6.剩余的数：列表中未被划除的数就是质数。

        7.结束：当处理完所有小于或等于√n的数后，列表中剩余的未被划除的数就是范围内的质数。

基本代码：

//本段代码是我自己写的，不一定标准，有需要的同学可以自己查标准的写法。
let arr=[]
for(let i=2;i<=100;i++){//模拟一个2到100的数组
    arr.push(i)
}
let l=0,r=Math.ceil(Math.pow(arr[arr.length-1],1/2))//l为第一个质数的索引，r为最后一个数开方向上取整
while(arr[l]<=r){//外层循环从第一个数到最后一个数的开方向上取整
    for(let i=l+1;i<arr.length;i++){//内层循环是整个数组
        if(arr[i]%arr[l]===0){//判断该数能否整除第一个质数，能的话就从数组中删除，并且索引减一（因为for循环后面有一个加一，删除后不减一就会跳过一个数字）
            arr.splice(i,1)
            i--
        }
    }
    l++//内循环结束后第一个质数后移一位
}
console.log(arr)

打印结果为[2，100]内所有质数

 说明：

        大家看到这应该会有很多疑问，比如：如果开头不是2怎么办，开头不是质数怎么办等等。我的理解只能将数组左侧扩充到2，然后在判断过程中加上对原来范围的控制，因为寻找质数的暴力方法只能是从2开始一个一个相除，所以该方法在寻找范围内所有质数在时间复杂度上已经有了很大的提升。

2.欧几里得算法，又名辗转相除法

适用场景：

        求两个数最大公因数

基本步骤：

        1.寻找两个数的较大数。

        2.使用较大数除以较小数，再使用本次计算中的除数除以余数

        3.重复步骤2，当余数为0时，本次计算的除数就是两个数最大公约数。

基本代码：

let a=12,b=18//任意定义两个数，为了方便所以定义的比较小，c为计算过程中的余数
if(b>a)[a,b]=[b,a]//保证a是较大数
while(1){//死循环，因为最大公因数一定有值，最小也是1
    let c=a%b
    if(c===0){//当余数为0就跳出循环，否则修改a和b的值，继续循环
        break
    }
    a=b
    b=c
}
console.log(b)//最后一次计算的除数就是最大公因数：6

原文地址：https://blog.csdn.net/Zrf2191318455/article/details/143977121

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！