质数判断

1. 让$i$从2枚举到$\sqrt{N}$，若对每一个$i$$n%i\neq0$，则是质数。否则是合数

2. Code

   int n;bool prime=true;
   for(int i=2;i*i<=n;i++)
           if(d%i==0)
           {
               prime=false;break;
           }
   

筛法

1. 用于计算哪些数字是素数

2. 用bool型变量作为桶，记录某个数是否为素数。

3. 埃式筛法

   1. 将isPrime[N]数组初始化为false，即均为质数。

   2. isPrime[0]=isPrime[1]=true;

   3. 从2开始枚举，若是质数，将其所有的倍数记录为合数。

   4. Code

      isprime[0] = isprime[1] = true;
      for (int i = 2; i * i <= n; i++)
      {
          if (!isprime[i])
          {
              for (int j = i * i; j <= n; j += i)
              {
                  isprime[j] = true;
              }
          }
      }
      

4. 线性筛法

   1. 用每个数的最小质因数进行标记。

   2. Code

      （有点问题，之后补）

GCD & LCM

1. GCD
   1. $GCD(a,b)=GCD(b,a%b)$。（辗转相除）
2. LCM
   1. $LCM(a,b)\times GCD(a,b)=a\times b$.

快速幂

1. $ans=a^b%p$时，快速求ans。

   ans = 1;
   while (b)
   {
       if (b & 1)
       {
           ans *= a;
           ans %= p;
       }
       a *= a;
       a %= p;
       b >>= 1;
   }
   cout << ans;