GCD LCM 素数 快速幂

1.**********  GCD(最大公约数)

 

代码实现（复杂度为O(logn)）

 

int gcd ( int a, int b){

    return b ? gcd ( b , a % b ) : a ;

}

 

2.***********   LCM（最小公倍数） 

 

lcm(a,b) = a * b / gcd(a,b);

 

3.********   素数

 

代码实现（复杂度为O(logn)）

 

函数isprime返回值中 值为1代表素数，值为0代表非素数

 

int isprime(int a){

    if(a==1) return 0;

    for(int i=2;i<=sqrt(a);i++){

        if(a%i==0) return 0;

    }

    return 1;

}

 

 

4.********素数打表

 

代码实现（复杂度为O(nloglogn)）

 

数组nisprime中 值为0代表素数，值为1代表非素数

 

const int MAXN = (int)（打表范围）;

int nisprime[MAXN];

void init() {

    nisprime[1] = 1;

    for(int i = 2; i < MAXN; i++) {

        if(!nisprime[i])

            for(long long j = i * i; j < MAXN; j += i) {

                nisprime[j] = 1;

            }

    }

}

 

//判断输入数值i是否为素数，只需判断nisprime[i]的值即可

 

5.********  快速幂

 

代码实现（复杂度为O(logn)）

 

#define ll long long

ll poww(ll a,ll b,ll c){

    ll ant=1;

    while(b){

        if(b&1) ant = (ant * a ) % c;

        a=a*a%c;

        b>>=1;

    }

    return ant;

}