自助网站系统,培训网站建设平台,wordpress添加字段,备案域名指向一个网站不管是在项目中还是面试时#xff0c;一定的算法能力都是极其重要的。大多数算法只要有一定的基础#xff0c;给足够的时间是可以写出来的#xff0c;然而有一类算法#xff0c;说难也不难#xff0c;说简单也不简单#xff0c;这种算法通常涉及到某种数学知识#xff0…不管是在项目中还是面试时一定的算法能力都是极其重要的。大多数算法只要有一定的基础给足够的时间是可以写出来的然而有一类算法说难也不难说简单也不简单这种算法通常涉及到某种数学知识如果了解这种知识那写出来就是易如反掌而没了解过相应知识的就只能使用暴力解法数据稍微多一点就超时甚至暴力都写不出来。本文就给大家讲解一下两种相关的数学知识。
1.埃拉托色尼筛法
适用场景 获取一段数字中所有的质数。
基本步骤 1.创建一个列表首先创建一个从2开始到你想要检查的数n包括n的连续整数列表。 2.标记第一个数从列表中的第一个数2开始因为它是第一个质数。 3.划除倍数从2的下一个数开始标记2的所有倍数。因为这些数都可以被2整除所以它们不是质数。 4.移动到下一个未标记的数在列表中找到下一个未被划除的数这个数就是下一个质数。对于这个新的质数重复步骤3划除它的所有倍数。 5.重复步骤继续这个过程每次都找到下一个未被划除的数并划除它的所有倍数直到你处理完所有小于或等于√n的数。因为一个数必须有一个因数小于或等于它的算数平方根。 6.剩余的数列表中未被划除的数就是质数。 7.结束当处理完所有小于或等于√n的数后列表中剩余的未被划除的数就是范围内的质数。
基本代码
//本段代码是我自己写的不一定标准有需要的同学可以自己查标准的写法。
let arr[]
for(let i2;i100;i){//模拟一个2到100的数组arr.push(i)
}
let l0,rMath.ceil(Math.pow(arr[arr.length-1],1/2))//l为第一个质数的索引r为最后一个数开方向上取整
while(arr[l]r){//外层循环从第一个数到最后一个数的开方向上取整for(let il1;iarr.length;i){//内层循环是整个数组if(arr[i]%arr[l]0){//判断该数能否整除第一个质数能的话就从数组中删除并且索引减一因为for循环后面有一个加一删除后不减一就会跳过一个数字arr.splice(i,1)i--}}l//内循环结束后第一个质数后移一位
}
console.log(arr)
打印结果为[2100]内所有质数 说明 大家看到这应该会有很多疑问比如如果开头不是2怎么办开头不是质数怎么办等等。我的理解只能将数组左侧扩充到2然后在判断过程中加上对原来范围的控制因为寻找质数的暴力方法只能是从2开始一个一个相除所以该方法在寻找范围内所有质数在时间复杂度上已经有了很大的提升。
2.欧几里得算法又名辗转相除法
适用场景 求两个数最大公因数
基本步骤 1.寻找两个数的较大数。 2.使用较大数除以较小数再使用本次计算中的除数除以余数 3.重复步骤2当余数为0时本次计算的除数就是两个数最大公约数。
基本代码
let a12,b18//任意定义两个数为了方便所以定义的比较小c为计算过程中的余数
if(ba)[a,b][b,a]//保证a是较大数
while(1){//死循环因为最大公因数一定有值最小也是1let ca%bif(c0){//当余数为0就跳出循环否则修改a和b的值继续循环break}abbc
}
console.log(b)//最后一次计算的除数就是最大公因数6
