判断素数

3²⁹   = 3 ¹    *    3 ⁴    *    3⁸   *    3¹⁶

1.一个质数的判断

bool judge(int n){
    if(n < 2){
        return false;
    }
    
    int bound = sqrt(n);
    
    for(int i = 0;i < bound;i++){
        if(n % i == 0){
            return false;
        }
    }
    
    return true;
}

2.快速幂

3²⁹   = 3 ¹    *    3 ⁴    *    3⁸   *    3¹⁶

29 = 11101(2)。对于n转化成二进制的每位，遇到0，倍乘；遇到1，将累乘的值乘到答案里。

//快速幂 求 x的n次方 结果的最后三位 
int quickPower(int x,int n){
    int answer = 1;
    int mod = 1000;
    while(n){ 
        if(n % 2){
            answer *= x;
            answer %= mod;
        }
        n>>1;//右移1位 
        x *= x; 
        x %= mod;
    } 
}