Songbirds


春

质数

  • ~5.15K 字
  1. 1. 1. gcd（最大公因数）
    1. 1.1. 1 辗转相除法
    2. 1.2. 2 使用java的API
  2. 2. 2. 判断一个数质数
  3. 3. 3.分解质因数
  4. 4. 4.获取1到n的所有质数
    1. 4.1. 4.1 暴力
    2. 4.2. 4.2 埃式筛
    3. 4.3. 4.3 欧拉筛（线性筛）
  5. 5. 5.LCM（最小公倍数）
    1. 5.1. 公式：最小公倍数= (a * b) / gcd(a, b )

质数相关

写这个的原因，主要是第 326 场周赛 - 力扣（LeetCode），多道题目考到了质数，也是本人第一场AK的周赛。LC给大家2023年的第一场福利周赛。

1. gcd（最大公因数）

求解两个数的最大公因数，例如24、30的最大公因数是6.

1 辗转相除法

辗转相除法的公式为：gcd(a,b) = gcd(b, a mod b)。具体示例如下：假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：

辗转相除法步骤
  • 1997 ÷ 615 = 3 (余 152)
  • 615 ÷ 152 = 4(余7)
  • 152 ÷ 7 = 21(余5)
  • 7 ÷ 5 = 1 (余2)
  • 5 ÷ 2 = 2 (余1)
  • 2 ÷ 1 = 2 (余0)
  • 1 ÷ 0 = ？
  • 直到b = 0，至此，最大公约数为a = 1

时间复杂度：对于gcd(a, b)，假设b <= a，则gcd的时间复杂度为O(logb)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 循环版
public int getGcd(int a, int b) {
    // 当b不等于0，即余数不等于0
    while (b != 0) {
        // 获得余数
        int rem = a % b;
        // 接下来计算gcd(b, a mod b)
        a = b;
        b = rem;
    }
    // b等于0了，
    return a;
}

// 递归版
public int getGcd2(int a, int b) {
    if (b == 0) {
        return a;
    }
    return getGcd2(b, a % b);
}

2 使用java的API

java的bigInteger有求解gcd的的API，但是必须把数字转为bigInteger。

1
2
3
4
5
6
public static int getGcd3(int a, int b) {
    BigInteger bigA = BigInteger.valueOf(a);
    BigInteger bigB = BigInteger.valueOf(b);
    BigInteger ans = bigA.gcd(bigB);
    return ans.intValue();
}

2. 判断一个数质数

使用试除法，如果能够整除以一个数，则说明不是质数。优化点，是我们只用试除到N\sqrt{N}即可，因为如果是合数（非质数），则N = a * b，（假设b <= a），则有b <= N\sqrt{N}成立。说明我们试除到N\sqrt{N}，就相当于尝试了所有可能的可以整除的数。

时间复杂度：O(N)O(\sqrt{N})。

1
2
3
4
5
6
7
8
9
public boolean isPrime(int a) {
    for (int i = 2; i * i <= a; i++) {
        // 能够整除i，说明是合数，不是质数
        if (a % i == 0) {
            return false;
        }
    }
    return true;
}

3.分解质因数

分解一个数的所有质因数。采用试除法，从最小的2开始。获取所有最小能够整除以的数。然后一直除下去。

时间复杂度：O(N)，在N是质数的情况下，达到最坏的情况。

更新：O(N\sqrt{N})，同判断一个质数，即使在最坏的情况下，我们也只需要试分解到O(N\sqrt{N})。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static List<Integer> getAllPrime(int a) {
    List<Integer> ansList = new ArrayList<>();
    int b = 2;
    while (b * b <= a) {
        // a能够整除以b
        if (a % b == 0) {
            // 则分解a
            ansList.add(b);
            // 分解后，a = a / b;
            a = a / b;
        } else {
            // 不能够整除以，则b+1
            b++;
        }
    }
    
    // 说明再经过操作之后 a 留下了一个素数
    if (a != 1) {
        ansList.add(a);
    }
    
    return ansList;
}

4.获取1到n的所有质数

4.1 暴力

采用判断一个数是否是质数的方法，从2判断到n，暴力的筛选出所有质数。
时间复杂读：不清楚^_^，大概范围是O(N) < t < O(N^2)

1
2
3
4
5
6
7
8
9
10
public List<Integer> getPrimes1(int n) {
    List<Integer> ansList = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        // 使用判断是否是质数的方法
        if (isPrime(i)) {
            ansList.add(i);
        }
    }
    return ansList;
}

4.2 埃式筛

埃式筛的代码比较简单，且复杂度也只多了loglogN，在不特别严苛的情况下使用埃式筛即可。

埃拉托斯特尼筛法，简称埃拉托斯特尼筛法_百度百科，要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去…。

时间复杂度：O(nloglogN)

埃式筛步骤
  • 列出2以后的所有序列：
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  • 标出序列中的第一个素数，也就是2，序列变成：
    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  • 将剩下序列中，划掉2的倍数，序列变成：
    2 3 5 7 9 11 13 15 17 19 21 23 25
  • 剩下的序列中第一个素数是3，将主序列中3的倍数划掉，主序列变成：
    2 3 5 7 11 13 17 19 23 25
  • 我们得到的素数有：2，3
  • 直到标出所有素数
    2 3 5 7 11 13 17 19 23

特别注意：筛法的方法建议写成静态的，然后静态调用。否则多次初始化会被LC卡掉。
另外大多数时候我们需要的最终结果集是一个SET。此筛法的ansList，不参与取值过程，可以直接改成set。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 设置成静态，避免多次调用TLE
private static final Set<Integer> primeSet = eulerFlagPrime((int) 4e6);

public static List<Integer> eratosFlagPrime(int n) {
    List<Integer> ansList = new ArrayList<>();
    // 筛选2到100的所有质数
    // 标记是否式质数，下标i代表数i，最大下标为100
    Boolean[] primeArr = new Boolean[n + 1];
    // 如果为null则代表为质数，省去遍历一遍改为true的时间
    for (int i = 2; i <= n; i++) {
        // 如果为null则为素数
        if (primeArr[i] == null) {
            ansList.add(i);
            // j 初始化为 2*i,每次遍历加一个i，相当于从2*i 到 k*i，从而划掉所有i的倍数
            for (int j = 2 * i; j <= n; j += i) {
                primeArr[j] = false;
            }
        }
    }
    return ansList;
}

4.3 欧拉筛（线性筛）

欧拉筛是对埃氏筛的改进，避免重筛，提高效率。但代码会更加复杂，只做介绍。

欧拉筛的核心思想就是确保每个合数只被最小质因数筛掉。或者说是被合数的最大因子筛掉。

欧拉筛步骤

比如说 1 ，2，3，4，5，6，7，8，9，10，11， 12
当 i=4时： primes = {2, 3}
此时i%2=0, 如果不结束内层循环的话,12会被3∗4筛掉， 当i=6时，12又会被2∗6筛掉。

特别注意：建议静态。同时ansList不能改成SET，在遍历ansList需要其有序，set会破坏这个有序。最后new HashSet<>(ansList)即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Integer> eulerFlagPrime(int n) {
    List<Integer> ansList = new ArrayList<>();
    Boolean[] primeArr = new Boolean[n + 1];
    for (int i = 2; i <= n; i++) {
        // 当前数式素数
        if (primeArr[i] == null) {
            ansList.add(i);
        }
        for (Integer prime : ansList) {
            if (i * prime > n) {
                break;
            }
            // 标记不为质数
            primeArr[i * prime] = false;
            if (i % prime == 0) {
                //避免重筛,使得程序更有效率
                break;
            }
        }
    }
    return ansList;
}

5.LCM（最小公倍数）

公式：最小公倍数= (a * b) / gcd(a, b )

1
2
3
public int lcm(a, b) {
    return (a * b) / getGcd(a, b);
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可