素数与最大公因子

素数

定义: 素数是大于 \(1\) 的正整数, 并且除了 \(1\) 和它本身外不能被其他正整数整除。

素数的数量: 不超过 \(N\) 的素数大约有 \(\frac{N}{\ln N}\) 个。

素性检验

人话: 判断一个数是否是素数。

试除法

原理: 如果一个数 \(x\) 能整除 \(n\) 那么 \(\frac{n}{x}\) 也一定能整除 \(n\) , \(x\) 与 \(\frac{n}{x}\) 中必定有一个数 \(\le \sqrt n\)。因此只需枚举 \([2,\sqrt n]\) 中每一个数，判读是否能整除 \(n\) 即可。

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

inline bool is_prime(int n)
{
    if(n<2)
        return false;
    for(register int i=2;i*i<=n;i++)
        if(!(n%i))
            return false;
    return true;
}

Miller-Robbin 算法

咕咕咕

素数筛法

埃拉托色尼斯筛法

素数与最大公因子

原文：https://www.cnblogs.com/isonder/p/14399022.html