质数

大于1的整数中只包含1和本身这两个约数，为质数

质数的判定——试除法

  bool is_prime(int n)  //O(sqrt(n))
 {
    if(n<2) return false;
    else
    {
        for(int i=2;i<=n/i;i++)
        {
            if(!(n%i)) return false;
        }
    }
    return true;
 }

分解质因数
思路；从小到大尝试所有的因数,是就n/=i

   void divide(int n)  //O(sqrt(n))
   {
       for(int i=2;i<=n;i++)
         if(n%i==0)
         {
             int s=0;
             while(n%i==0)
             {
                 n/=i;
                 s++;
             }
             cout<<i<<' '<<s<<endl;
         }
      return ;
   }
   // 改良版
   void divide(int n)
   {
       for(int i=2;i<=n/i;i++)
         if(n%i==0)
         {
             int s=0;
             while(n%i==0)
             {
                 n/=i;
                 s++;
             }
             cout<<i<<' '<<s<<endl;
         }
        if(n>1)  cout<<n<<' '<<'1'<<endl;
      return ;
   }

筛素数法

   void get_prime(int n)
   //埃氏筛法O(nlog(log(n))) 
   {
       for(int i=2;i<=n;i++)
       {
           if(!st[i]) 
           {
           prime[cnt++]=n;
           for(int j=2*i;j<=n;j+=i) st[i]=true; 
           }
       }
   }

   //线性筛法 每一个数只会被它的最小质因子筛掉
   每次只要筛选小于等于i的第一个素因子的素数与i的乘积，既不会造成重复筛选，又不会遗漏， 时间复杂度O(N)。
   void   get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) 
        {
            prime[cnt++]=i;
        }

        for(int j=0;prime[j]*i<=n;j++)//筛除 prime[j]*i,直到prime[j]
        //是i的最小质因子
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;

        }

    }
}