素数，模幂高效计算技巧

高效寻找素数

204. 计数质数

使用素数筛选法

首先从 2 开始，我们知道 2 是一个素数，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8… 都不可能是素数了。

然后我们发现 3 也是素数，那么 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12… 也都不可能是素数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countPrimes(int n) {
        boolean isPrime[]=new boolean[n];
        Arrays.fill(isPrime,true);
        for(int i=2;i*i<=n;i++){
            if(isPrime[i]){
                for(int j=i*i;j<n;j+=i){
                    isPrime[j]=false;
                }
            }
        }
        int ans=0;
        for(int i=2;i<n;i++){
            if(isPrime[i]){
                ans++;
            }
        }
        return ans;
    }
}

高效模幂计算

超级次方

返回幂运算 a^b 的计算结果与 1337 取模后的结果

  • 指数b非常大，以数组的形式给出
image-20221115105025794

递归计算

  • 模运算技巧

对于形如 (a * b) % base 这样的运算，乘法的结果可能导致溢出。

(a * b) % k = (a % k)(b % k) % k

image-20221115105906252

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    static final int MOD=1337;
    public int superPow(int a, int[] b) {
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<b.length;i++){
            list.add(b[i]);
        }
        return computerPow(a,list);
    }

    int computerPow(int a,List<Integer> list){
        if(list.isEmpty() || list.size()==0){
            return 1;
        }
        int t=list.remove(list.size()-1);
        int part1=myPower(a,t);
        int part2=myPower(computerPow(a,list),10);
        return part1*part2 % MOD;
    }

    // 求a的k次方余上MOD的结果
    int myPower(int a,int k){
        // 对因子求模，每次乘法结果再求模
        a=a%MOD;
        int res=1;
        for(int i=0;i<k;i++){
            res*=a;
            res=res%MOD;
        }
        return res;
    }
}

更高效的快速求幂

image-20221115112224369

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 // 求a的k次方余上MOD的结果
static int myPower(int a,int k){
    if(k==0){
        return 1;
    }
    // 对因子求余
    a=a%MOD;
    if(k%2==1){ // k是奇数
        return (a*myPower(a,k-1))%MOD;
    }else{  // k是偶数
        int sub= myPower(a,k/2);
        return (sub*sub)%MOD;
    }
}