质数

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。定义质数又称素数。

试除法判定质数

$$ 试除法判定质数就是从定义出发，除了1和它本身以外不再有其他因数 $$

$$ 我们可以从判断[2, n]中是否有它的因子 $$

$$ 我们没必要把所有[2, n]的数都进行判断，只需要判断到\sqrt{n}即可 $$

$$ 证明：假设a|n则 \frac{n}{a}|n,则min(\frac{n}{a}, a)|n $$

$$ 所以只需要遍历到满足a^2<=n的a即可 $$

分解质因数

$$ 将一个数n分解成p_1^{q_1}p_2^{q_2}p_3^{q_3}\cdots p_m^{q_m}(p_1,p_2,p_3\cdots p_m均为质数) $$

$$ 枚举[2, n]中所有n的因数a，并计算a的次数即可，不是应该枚举质因数吗？ $$

$$ 证明：当我们枚举到a时，我们已经对[2, a - 1]的数都进行了判断，此时存在a|n $$

$$ 假设a为合数，则[2, a - 1]中一定存在b使得b|a,则b|n $$

$$ 但是[2, a - 1]中的数已经被n除过了所以一定不存在 $$

$$ b|n,与假设矛盾，则a一定为质数。 $$

$$ 同时我们也不需要将[2, n]中的数都进行枚举，只需要枚举到\sqrt{n}即可。 $$

$$ 但是此时我们只枚举到所有小于等于\sqrt{n}的质因数，会有漏判>\sqrt{n}的大质因数的可能 $$

$$ 如 28=2^2 \times 7而 \sqrt{28} < 6,枚举不到 7 这个质因数 $$

$$ 实际上 28 / 2 ^ 2 = 7,此时 n 就是留下的大质因数本身 $$

$$ 可以证明这样的大质因数最多只有一个且次数唯一 $$

$$ 所以在循环之后判断一下n > 1即n是否除尽即可。 $$

质数筛

埃氏筛法

$$ 枚举所有没被筛的数（这些数一定是质数），将这些数的倍数筛掉 $$

$$ 时间复杂度O(\log^{\log^{n}}) $$

线性筛法

$$ 我们知道用埃氏筛法有的数会被重复筛除，线性筛法的思想就是每个合数的最小质因子来筛除它。 $$

$$ 由于一个数的最小质因子，只有一个所以一个数最多只被筛一次，时间复杂度O(n) $$

for (int i = 2; i <= n; i++) {
            if (!isVis[i]) {
                prime[count++] = i;
            }
            for (int j = 0; prime[j] <= n / i; j++) {
                isVis[i * prime[j]] = true;
                if (i % prime[j] == 0) {
                    break;
                }
            }
 }

$$ 满足!isVis的i表示未被筛除即为素数，而无论i是质数还是合数都需要用来筛数 $$

$$ 内层循环中 i \times prime[j]一定是合数需要被筛除 $$

$$ 此时prime[j]就是 i \times prime[j]的最小质因子 $$

$$ 为什么prime[j]一定是最小质因子呢？以下prime[j]均简称为p_j $$

$$ 证明：我们关注后置的if语句，假设i为合数 $$

$$ 因为p_j|i，所以p_j就是i的最小质因子，则p_j\times{i}的最小质因子也是p_j $$

$$ 假设i为质数，则if成立的条件就是i == p_j，此时p_j\times{i}的最小质因子为i也等于p_j $$

$$ 所以无论如何p_j一定是最小质因子，符合只是用最小质因子来筛选的算法思路 $$

AcWing 866. 试除法判定质数 原题链接

给定n个正整数aiai，判定每个数是否是质数。

输入格式

第一行包含整数n。

接下来n行，每行包含一个正整数aiai。

输出格式

共n行，其中第 i 行输出第 i 个正整数aiai是否为质数，是则输出“Yes”，否则输出“No”。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤231−11≤ai≤231−1

输入样例：

2
2
6

输出样例：

Yes
No

private static boolean check(int x) {
        if (x <= 1) return false;
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

AcWing 867. 分解质因数 原题链接

给定n个正整数aiai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数n。

接下来n行，每行包含一个正整数aiai。

输出格式

对于每个正整数aiai,按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2∗1091≤ai≤2∗109

输入样例：

2
6
8

输出样例：

2 1
3 1

2 3

private static void decompose(int x) {
        for (int i = 2; i <= x / i; i++) {
            int mul = 0;
            if (x % i == 0) {
                while (x % i == 0) {
                    mul++;
                    x /= i;
                }
                out.println(i + " " + mul);
            }
        }
        if (x > 1) out.println(x + " " + 1);
}

AcWing 868. 筛质数 原题链接

给定一个正整数n，请你求出1~n中质数的个数。

输入格式

共一行，包含整数n。

输出格式

共一行，包含一个整数，表示1~n中质数的个数。

数据范围

1≤n≤1061≤n≤106

输入样例：

8

输出样例：

4

埃氏素筛

    static int[] primes;
    static int count;
    static boolean[] isVis;
    public static void main(String[] args) {
        int n = in.nextInt();
        primes = new int[n + 1];
        isVis = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            if (!isVis[i]) {
                primes[count++] = i;
                for (int j = i + i; j <= n; j += i) {
                    isVis[j] = true;
                }
            }
        }
        out.println(count);
        out.flush();
        out.close();
    }

线性素筛

    static int[] prime;
    static int count;
    static boolean[] isVis;
    private static void primeSieve(int n) {
        for (int i = 2; i <= n; i++) {
            if (!isVis[i]) {
                prime[count++] = i;
            }
            for (int j = 0; prime[j] <= n / i; j++) {
                isVis[i * prime[j]] = true;
                if (i % prime[j] == 0) {
                    break;
                }
            }
        }
    }