质数

质数：在大于1的正整数中，如果只有1和本身两个约数，就是质数。或者叫素数。

（1）判定素数——试除法

1.1 时间复杂度O（N）

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

数据范围2^31==2^10，运行超时会。

这里是i<n;

1.2时间复杂度O（sqrt(N)）

知识点：

               二的三十一次方是2147483648,也就是等于int 的最大的表示范围；因为int 是4个字节，每个字节8个bit位置，最高位是符号位，还剩余31位置。

               |  整除符号;

               a|b   a可以整除b==b除以a余数数0;

               若a|b则b/a|b,b/a可以整除b;

               可知：约数是成对出现的，我们可以枚举较小的数字。

               即判断条件  i<=N/i;  等于号是为了对于完全平方数。

              可以等价于 i<=sqrt(N);但是不推荐，因为sqrt()特别慢。