常用算法模板总结（1）----快速，最大公约数，最小公倍数，求一个数的所有因数之和，素数判断

本文主要是介绍常用算法模板总结（1）----快速，最大公约数，最小公倍数，求一个数的所有因数之和，素数判断，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.快速幂模板。

快速幂的模板大家应该是不陌生的，之前我一直是直接记模板的，今天来具体解释一下快速幂模板的意义。

不取模的模板如下：（取模自己修改一下）

ll fp(ll a,ll b){
	ll ans=1;
	ll base=a;
	while(b!=0){
		if(b&1!=0)
           ans=ans*base;
        base*=base;
        b>>=1;
	}
	return ans;
} 

如何理解该模板：

首先快速幂的基本思想是分治和二进制，我们直接带入一个例子更好理解，如计算2的11次方。

首先ans=1,base=2,b=11;我们知道11的二进制是1011；if(b&1!=0) ans=ans*base;这一个语句的作用是，根据幂的二进制来决定是否要乘入答案，base*=base;的作用是让基数翻倍；

   拿2的11次方来说，①b=1011,ans=1,base=2 ②ans=1*2,base=2*2,b=101, ③ans=2*2*2，base=2*2*2*2，b=10  ④ans=2*2*2，base=2*2*2*2*2*2*2*2,b=1 ⑤ ans=2*2*2*2*2*2*2*2*2*2*2,b=0 ⑥跳出for循环，结束。

这么理解一下，快速幂的模板再也不用四级硬背了，信手拈来。

由上可见，达到了计算2的11次方的目的，最坏的复杂度也只为O(logn)，而暴力的复杂度是O(n),快速幂简直是完美情人！

2.求两个数的最大公约数模板

（1）经典欧几里得算法（辗转相除法）一般用这个就够了

int gcd(int a,int b){
	if(b==0) return a;
	else return gcd(b,a%b);
}

如何理解记忆：

写题最讨厌的就是找代码模板了，所以我们要做到让这些常用代码印在心中！

其实就是两个数反复换位相互求余，当b为0时，a即为最大公因数。

如计算8和12的最大公因数，gcd(8,12),gcd(12，8)，gcd(8,4),gcd(4,0)。

推导一遍就很容易记下。欧几里得算法依旧是复杂度为O（logn）的优秀算法。

（2）stein算法（如果不能A题，用这个改进一下）

针对欧几里德算法在对大整数进行运算时，需要试商导致增加运算时间的缺陷而提出的改进算法。

ll gcd(ll u,ll v)
{
    if (u == 0) return v;
    if (v == 0) return u;
    if (~u & 1) 
    {
        if (v & 1) 
            return gcd(u >> 1, v);
        else 
            return gcd(u >> 1, v >> 1) << 1;
    }
    if (~v & 1) 
        return gcd(u, v >> 1);
    if (u > v)
        return gcd((u - v) >> 1, v);
    return gcd((v - u) >> 1, u);
}

直接贴代码，因为也不常用，没有去理解，用得上的机会比较少。

3.最小公倍数。

求两个数的最小公倍数算法是基于gcd算法的基础上的。

int lcm(int a,int b){
	return a/gcd(a,b)*b;
}

如何理解记忆：

这个还是比较简单的，就是用一个数去除以最大公因数得到的结果，再乘以另一个数，就可以得到这两个数的最小公倍数。

4.求一个数的所有因数之和。

（包括一，不包括本身）算法的解释都在代码里面了，比较好理解。

int factorSum(int n){
	    int sum=0;
    for (int i=1;i*i<=n;i++){//折半除，降低复杂度
        if (n%i==0){
            if (i==1||i*i==n) sum+=i;//如果这个因数为1或者刚好是该数的平方根，只加一个就可以了。
            else	sum+=i+n/i;//加上该因数和该因数的关联因数。
        }
    }
    return sum;
}
    

5.素数判断

（1）一般情况下，简单的判断素数代码。

bool is_prime(int n){
	if(n<=1) return false;
	for(int i=2;i*i<=n;i++)
	   if(n%i==0) return false;
	return true; 
}

这个比较好理解，只要有除1以外的因数直接返回false，否则返回true

复杂度O(根号n)，这个模板的时间复杂度对于10的12次方以内的数的判断是没有问题的

（2）更快速的方法

这两个方法在数据不是很大时对比不明显，数据很大时可以体现出方法2的优越性。代码如下：

bool isPrime(int a) {
    if(a == 1) return 0;
    if(a == 2 || a == 3) return 1;
    if(a%6 != 1 && a%6 != 5) return 0;
    int sqrtA = sqrt(a);
    for(int i = 5; i <= sqrtA; i += 6) {
        if(!(a%i)|| !(a%(i+2))) return 0;
    }
    return 1;
}

如何理解记忆：

这个的理解过程就比较长了。【素数的判定-从暴力到高效】-C++ - 摸鱼酱 - 博客园 (cnblogs.com)

可以去博客园看一下这篇比较详细的博客，搬运一下。

看到这里，感谢观看，写了这么久，点个赞吧，嘿嘿嘿，下次见。

这篇关于常用算法模板总结（1）----快速，最大公约数，最小公倍数，求一个数的所有因数之和，素数判断的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！