1 - 质数

算法题冲冲冲！

质数的定义

在大于1的整数中，如果只包含1和它本身这两个约数，就被称为质数，或者叫素数。

质数的判定

根据定义本身出发，我们可以通过试除暴力枚举每个数，判断它是不是质数，时间复杂度为$O(N)$。

考虑到如果$y$是$x$的因数，那么$\frac{x}{y}$也是$x$的因数，因此只需校验$y$或$\frac{x}{y}$即可。经统计发现，这两个数的较小数分布为$[2,\sqrt{x}]$，那么只需遍历该区间内所有数即可，时间复杂度降低至$O(\sqrt{x})$。

代码如下：

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

质数的应用

质数筛

如果只按照上边的方法去判定质数，会发现效率很慢。这里介绍两种快速的质数筛法：埃式筛法 和 线性筛法。

埃式筛法

根据 一个质数的倍数肯定不是质数 这一原理，可以快速筛选出一些质数。

int primes[N], cnt;
bool st[N];

// 获取从2~n间的所有质数
void getPrimes(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            for (int j = i + i; j <= n; j += i)
            {
                st[j] = true;
            }
        }
    }
}

算法的时间复杂度为$O(N\log\log N)$。

线性筛法

数据规模超过$10^7$时效率比埃式筛法好。原理是 n只会被它的最小质因子筛掉 ：

代码如下：

int primes[N], cnt;
bool st[N];

void getPrimes(int n)
{
    for (int i = 2; i <= n; ++i)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; ++j)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}

时间复杂度为$O(N)$。

分解质因数

可用试除法，从小到大枚举所有因数：

void divide(int n)
{
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0)
            {
                n /= i;
                ++s;
            }
            cout << i << " " << s << endl;
        }
    }
    // 别忘了还有1和它本身
    if (n > 1)
        cout << n << " " << 1 << endl;
}

时间复杂度为$O(\sqrt{N})$。

练习题

质数筛

204. 计数质数 - 力扣（LeetCode）

分解质因数

2521. 数组乘积中的不同质因数数目 - 力扣（LeetCode）

参考资料

• 算法基础课 - AcWing