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的正整数都能唯一分解为有限个质数的乘积，可写作：

其中\(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\) 的个数。