质数

本标题下所有数 $x\in N^*$ 。

单个质数的判定

思想

枚举 $i\in{{1\sim\sqrt{P}}}$​​ ，判断$P\mod{i}$​​​​是否为$0$​即可。

若数 $P=p_1*p_2$​ 并且 $p_2>\sqrt{P}$​ ​​，则 $p_1<\sqrt{P}$​ ,所以只需要枚举 $i$​ 到 $i<=\sqrt{P}$​ 。

代码

bool prime(int n)
{
    int len = sqrt(n);//求i的遍历范围
    for (int i = 2; i <= len; i++)
        if (!(n % i))//如果i是n的约数，说明n不是质数，返回false
            return false;
    return true;//n除了1和n以外没有别的约数，证明n是质数，返回true
}

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

单个数分解质因数

想法和上面的一样，只不过找到一个因数就循环除他罢辽。

list<int> prime(int n)
{
    list<int> result;
    int len = sqrt(n); //求i的遍历范围
    for (int i = 2; i <= len; i++)
    {
        if (N % i == 0)
        { // 如果 i 能够整除 N，说明 i 为 N 的一个质因子。
            while (N % i == 0)
                N /= i;
            result.push_back(i);
        }
    }
    if (N != 1)
    { // 说明再经过操作之后 N 留下了一个素数
        result.push_back(N)
    }
}

范围内所有质数的判定

纯暴力

就把上面那个套个循环，复杂度 $O(n\sqrt n)$。

埃氏筛

从 $2$ 开始，不断寻找没有被标记的，并把它的倍数全部标记，复杂度 $O(n\log\log n)$。

但是，我们注意到，某一些合数被标记了不止一次，因此仍有优化空间。

欧拉筛