0x31 质数 | 质数

质数

定义：

若一个大于1的数的因数只有1和它本身，那么称该数为质数（素数），否则称其为合数。

素数分布定理
设$x≥1$，以$π(x)$表示不超过$x$的素数的个数，当$x→∞$时，$π(x)～x/ln(x)$。

质数的判定(试除法)

定理：
若一个数$N$为合数，则$N$必存在一个大于 $1$ 小于等于$\sqrt N$的因数。

证明：假设$N$不存在小于等于$\sqrt N$的因数。

按定义，$N$至少存在一个大于1小于$N$的因数，记该数为$a$.
那么 $N = a * x$，其中$x = N / a$。
若$a$和$x$均大于$\sqrt N$，那么$ a * x > N$，与前面矛盾，故假设不成立。

bool is_prime(int n)
{
    if (n < 2) return false;
    int k = sqrt(n);
    for (int i = 2; i <= k; i++)
        if (n % i == 0) return false;
    return true;
}

例1.

房间里面有$N$盏关着的灯，编号依次为$1，2， 3，。。。，N$，有$N$个人，他们的编号也依次为$1，2， 3，。。。，N$，现这$N$个人依次走入房间，每人将编号为自己编号倍数的灯的开关按钮按下一次，这样灯的熄亮状态就会切换一次。在这$N$个人完成他们的操作后，输出最后亮着的灯。

质数的筛法

埃氏筛法

原理：任意整数 $x$ 的倍数 $2x$ , $3x$ , ...均是合数。

prime[1] = 1;
for (int i = 2; i <= n; i++)
{
    for (int k = 2; k <= n / i; k++)
        prime[k * i] = 1;
}

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

优化1. 在筛$x$的倍数的时候，可以只考虑质数，因为若x是合数，那么数可以被比$x$更小的质因数筛掉。

优化2. 在筛质数x的倍数的时候，可以从$x^2$开始考虑，因为小于$x^2$的x的倍数会被更小的质数筛掉。

prime[1] = 1;
for (int i = 2; i <= n; i++)
{
    if (prime[i]) continue; // 优化1
    for (int k = i; k <= n / i; k++)  // 优化2
        prime[k * i] = 1;
}

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

线性筛法

原理：保证每个合数仅被其最小的合数筛掉一次。

bool vis[1000];
int prime[10000];
int cnt = 0;
for (int i = 2; i <= n; i++)
{
    if (!vis[i]) prime[++cnt] = i;
    for (int j = 1; j <= cnt && i <= n / prime[j]; j++)
    {
        vis[i * prime[j]] = 1;
        if (i % prime[j] == 0)
            break;
    }
}

质因数分解

算术基本定理

任何一个大于1的正整数都能唯一分解为有限个质数的乘积，可写作：
\[N=p_1^{c_1}p_2^{c_2}...p_m^{c_m}\]
其中$c_i$都是正整数，$p_i$都是质数，且满足$p_1 < p_2 <... < p_m$。

试除法

void divide (int n)
{
    m = 0;
    int sq = sqrt(n);
    for (int i = 2; i <= sq; i++)
    {
        if (n % i == 0)
        {
            p[++m] = i, c[m] = 0;
            while (n % i == 0) c[m]++;
        }
    }
    if (n > 1) p[++m] = n, c[m] = 1
}

时间复杂度$O(\sqrt n)$

例2

给定两个整数L和U，你需要在闭区间$[L,U]$内找到距离最接近的两个相邻质数$C_1$和$C_2$（即$C_2-C_1$是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数$D_1$和$D_2$（即$D_1-D_2$是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

数据范围：
$1≤L<U≤2^{31}−1$
其中$L$和$U$的差值不会超过1000000
时空限制：
1s / 64MB

例3

给定整数$N$ ，试把阶乘$N!$分解质因数，按照算术基本定理的形式输出分解结果中的$p_i$ 和 $c_i$ 即可。

输入格式
一个整数$N$。

输出格式
$N!$ 分解质因数后的结果，共若干行，每行一对$p_i$, $c_i$，表示含有$p_i^{c_i}$项。按照$p_i$从小到大的顺序输出。

数据范围
$1≤N≤10^6$

例4

给定整数$N$ ，试求出阶乘$N!$末尾 $0$ 的个数。