前置

1. 萌新一只，代码 不简洁 / 可读性不强。
2. 现在只是初一一只，对于很多概念不太熟悉。

part 1 暴力判断

思路十分简单，只需要从 $2$ 枚举到 $x-1$，若 $x\ mod\ i\ =\ 0$，则 $x$ 不是质数。

小优化：

由于只需一个数能被整除即非质数，所以当 $x\ mod\ i\ =\ 0$ 时可以立刻结束判断。

Code:

bool prime (int x)
{
    if (x <= 1) return 0;

    for (int i = 2; i < x; i ++)
        if (!(x % i)) return 0;

    return 1;
}

对于任意一个质数，暴力判断的时间复杂度是 $O(N)$；优化后的是 $O(Nlog_2(N))$。

part 2 试除法

这种方法基于 暴力判断 的思路上。

假设 $\forall 2 \le i \le x-1$ 且 $x\ mod\ i\ =\ 0$，则必有 $j = x \div i$，使得 $x\ mod\ j\ =\ 0$。

而对于任意一个正整数，$(\sqrt x) ^ 2$ 必定大于等于 $x$。再根据刚刚的思路，我们就可以将 $\sqrt x + 1$ 至 $x$ 的一段判断省略。

对于任意一个质数，暴力判断的时间复杂度是 $O(\sqrt N)$。对于一个非质数，时间复杂度与优化过的暴力判断无异（这个想都不用想就知道了）。

Code:

bool prime (int x)
{
    if (x <= 1) return 0;

    for (int i = 2; i <= sqrt(x); i ++)
        if (!(x % i)) return 0;

    return 1;
}

part 3 Miller_Rabin 判断素数

其理太深，自知非吾事（会写不会解释），先暂时只贴码了。

int qmi (int base, int exp, int mod)
{
    if (!exp) return 1;

    int res = 1 % mod;
    while (exp)
    {
        if (exp & 1)
            res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

bool judge (int a, int m, int p, int n)
{
    int tmp = qmi (a, m, n), res;

    for (int i = 1; i <= p; i ++)
    {
        res = qmi (tmp, 2, n);
        if (res == 1 && tmp != n - 1 && tmp != 1)
            return 1;
        tmp = res;
    }
    return res != 1;
}

bool Miller_Rabin (int x)
{
    if (x== 2) return 1;
    if (x < 2 || ! (x & 1))
        return 0;

    int n = x - 1, j = 0;

    while (! (n & 1))
        n >>= 1, ++ j;

    for (int i = 1; i <= 10; i ++)
    {
        int a = rand () % (x - 1) + 1;
        if (judge (a, n, j, x)) 
            return 0;
    }

    return 1;
}

part 4 埃氏筛

前面讲的三种方法都是对于一个数的判断。而埃氏筛是快速找出 $1$ 至 $n$ 中所有质数。

首先，我们举个小小的例子：集合 $2$ 到 $10$，现在我们对它进行几个操作：

1. 将其中所有 $2$ 的倍数（不包括本身，下面的操作也如此）删掉。现在集合中只剩下 ${2, 3, 5, 7, 9}$ 五个数字。
2. 将其中所有 $3$ 的倍数删掉。现在集合中只剩下 ${$2, 3, 5, 7}$ 四个数字。

我们现在已经可以发现，剩下的数字全部都是质数了。那么我们是不是可以用这种思路在保证效率的情况下将 $n$ 以内的非质数删掉呢？

首先清楚一下质数的概念：因数只有两个。对于任意一个非质数，我们都可以有一个 $j, k\left(1 \le j,k \le n\right)$，使得 $j \times k = n$。所以上述思路正确，我们可以在 $O(Nlog_2(N)$ （大概，不太精确）的时间内求出 $1$ 到 $N$ 内的质数。

然后我们可以对它进行亿点点优化。对于一个 $x$，它所能排的数它的因数都已经排掉了。所以我们只需要对质数进行排数操作，现在我们的复杂度已经优化到了 $Nlog_2(log_2(N))$；代码不给了，就看下面优化的吧~

Part 5 欧拉筛质还可以优化到 $O(N)$，但懒得写了，所以就给个代码就算了。

void Eroto (int n)
{
    memset (vis, 0, sizeof vis);
    for (int i = 2; i <= n; i ++)
    {
        if (!vis[i])
        {
            vis[i] = i;
            p[++ m] = i;
        }

        for (int j = 1; j <= m; j ++)
        {
            if (p[j] > vis[i] || p[j] > n / i) 
                break;
            vis[i * p[j]] = p[j];
        }
    }
    return;
}