试除法判断质数 $ O(\sqrt{N}) $
cpp
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )//写i*i<=x容易爆int,写i<=sqrt(x)太慢
if (x % i == 0)
return false;
return true;
}