欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

GCD LCM 素数 快速幂

程序员文章站 2022-03-24 22:47:04
1.********** GCD(最大公约数) 代码实现(复杂度为O(logn)) int gcd ( int a, int b){ return b ? gcd ( b , a % b ) : a ; } 2.*********** LCM(最小公倍数) lcm(a,b) = a * b / gc ......

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;

}