素数(质数)

他的定义是：除了1和他本身，没有其他因数。
所以可以得出 2,3,5,7...都是质数

判断算法

• 暴力
  只需要找到一个不大于他本身的因数就不是质数，暴力枚举，复杂度高
• 暴力优化
  我们只需要枚举到 S q r t ( n ) Sqrt(n) Sqrt(n)就行了，只要之前没有出现因数，后面也不会出现

bool isPrime( int num )
{
     int tmp =sqrt(num);
     for(int i= 2;i <=tmp; i++)
        if(num %i== 0)
          return 0 ;
     return 1 ;
}

• 数学定理
  首先要知道所有的自然数都可以表示为
  6 x , 6 x + 1 , 6 x + 2 , 6 x + 3 , 6 x + 4 , 6 x + 5 6x,6x+1,6x+2,6x+3,6x+4,6x+5 6x,6x+1,6x+2,6x+3,6x+4,6x+5
  其中 6 x , 6 x + 2 , 6 x + 3 , 6 x + 4 6x,6x+2,6x+3,6x+4 6x,6x+2,6x+3,6x+4都分别能被 6 , 2 , 3 , 2 6,2,3,2 6,2,3,2整除
  所以只剩下 6 x + 1 , 6 x + 5 6x+1,6x+5 6x+1,6x+5可能是素数
  所以只需要枚举 6 x + 1 , 6 x + 5 6x+1,6x+5 6x+1,6x+5新式的数，同时注意到 6 x + 1 , 6 x + 5 6x+1,6x+5 6x+1,6x+5只有可能被形如 1 + 6 x , 5 + 6 x 1+6x,5+6x 1+6x,5+6x的数整除，所以代码写成这样

bool isPrime(int n)
{
    if(n==2||n==3)
        return true;
    if(n%6 != 1 || n%6 != 5)
        return false;
    int t = sqrt(n);
    for(int i = 5;i<=t;++i)
    {
        if(n%i == 0 || n%(i+2)==0)
        {
            return false;
        }
    }
    return true;
}

复杂度分析

实测得出
O 3 < O 2 < < O 3 O_3 <O_2<<O_3 O3​<O2​<<O3​