C++质数相关

1.判断质数

1.单一判断

用作判断次数不多时使用。

bool is_prime(int x)
{
    if(x <= 1)
    {
        return 0;
    }
    for(int i = 2 ; i * i <= x ; i ++)
    {
        if(x % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

解释：我们把一个数拆成 $x \times y$，发现永远 $x$ 小于 $\sqrt n$，所以只要 $n$ 不能整除 $\le \sqrt n$ 的整数，就是一个质数，提高了很多效率。但要注意，$n \le 1$ 需单独处理。

2.埃氏筛法

当我们要进行多次判断时，就可能需要用到埃氏筛法。小学数学课讲过，放个图片应该就能理解。

isn_t_prime[0] = isn_t_prime[1] = 1;
for(int i = 2 ; i <= 1e6 ; i ++)
{
    if(isn_t_prime[i])
    {
        continue;
    }
    for(int j = 2 ; i * j <= 1e6 ; j ++)
    {
        isn_t_prime[i * j] = 1;
    }
}

解释：为了省去初始化数组全部为 $1$ 的时间，$0$ 才代表这是一个质数。碰到一个没达标记的数，就把它的倍数全部打上标记，重复标记是没问题的。但 $n$ 要 $\le 10^6$，不然容易超时，$n \ge 10^6$ 时，还是用方法一较为合适。