质数相关模板 - l00jj/algorithm GitHub Wiki

注意：

！质数的处理环节放在 static {} 并不一定比放在正式环节内要快，可以尝试更换生成位置看是否有速度提升！

高效提取质因数

class Solution {
    private static final int[] MIN_PRIME;

    static {
        MIN_PRIME = new int[1_000_001];
        int[] prime = new int[1_000_001];
        int count = 0;
        for (int i = 2; i < prime.length; i++) {
            if (MIN_PRIME[i] == 0) {
                MIN_PRIME[i] = prime[count++] = i;
            }
            for (int j = 0; j < count && i * prime[j] < prime.length; j++) {
                MIN_PRIME[i * prime[j]] = prime[j];
                if (i % prime[j] == 0) break;
            }
        }
    }


            //【方案一】使用代码，核心在于反复寻找当前最小质因数
            for (int num = input; num > 1; num /= MIN_PRIME[num]) {}
                 // 注意：for循环内逻辑代码部分，使用的是MIN_PRIME[num]，不是num

            //【方案二】有需要时用一个变量循环剔除重复出现的质数
            for (int num = input, same = 0; num > 1; num /= MIN_PRIME[num]) {
                if (MIN_PRIME[num] == same) continue;
                // 逻辑代码，注意变量用MIN_PRIME[num]，而不是num
                same = MIN_PRIME[num];
            }
}

快速分解质因数，示例代码

    // 寻找因数
    for (int factor = 2; factor * factor <= num; factor++) {
        if (num % factor == 0) {
            // 逻辑代码区
            // ...
            // 找到因数后把对应倍数剔除
            while(num % factor == 0) num /= factor;
        }
    }
    // 结果也是一个质因数
    if (num > 1) {
        // 逻辑代码区
        // ...
    }

预处理质数筛

函数内使用版

    static int[] primes;
    static {
        int max = (int)1e6; // 最大搜索数
        boolean[] visted = new boolean[max + 1];
        primes = new int[100];
        primes[0] = 2;
        primes[1] = 2;
        for (int cNum = 2; cNum <= max; cNum += 2) visted[cNum] = true;
        for (int num = 3; num <= max; num += 2) {
            if (!visted[num]) {
                if (primes[0] == primes.length) {
                    int[] resPrimes = new int[primes.length * 10];
                    System.arraycopy(primes, 0, resPrimes, 0, primes.length);
                    primes = resPrimes;
                }
                primes[primes[0]++] = num;
            }
            for (int cNum = num; cNum <= max; cNum += num) {
                visted[cNum] = true;
            }
        }
        int[] resPrimes = new int[primes[0] - 1];
        System.arraycopy(primes, 1, resPrimes, 0, resPrimes.length);
        primes = resPrimes;
    }

类静态/外置版

class Solution {
    private final static int MX = (int) 1e6;
    private final static int[] primes = new int[78498];
    private final static boolean[] np = new boolean[MX + 1];

    static {
        int pi = 0;
        for (int i = 2; i <= MX; ++i) {
            if (!np[i]) {
                primes[pi++] = i;
                for (int j = i; j <= MX / i; ++j) np[i * j] = true;
            }
        }
    }
}

MX = 10 ** 6 + 1
primes, is_prime = [], [True] * MX
for i in range(2, MX):
    if is_prime[i]:
        primes.append(i)
        for j in range(i * i, MX, i):
            is_prime[j] = False

单个数字判断

如果数量不多情况下直接判断更为简单

    def is_prime(self, n: int) -> bool:
        return all(n % i for i in range(2, isqrt(n) + 1))
    is_prime = lambda n: n >= 2 and all(n % i for i in range(2, isqrt(n) + 1))

相关题目：