质数

在大于1的整数中，如果只包含1和其本身这两个约数，就被称为质数，或者素数。

1.质数的判定

一般我们习惯使用—–试除法(sqrt(N))

即

for (int i = 2; i <= n / i; i ++)
{
    if(n % i == 0){
        .....
    }
}

2.分解质因数—–试除法

• 质因数（素因数或质因子）在数论里是指能整除给定正整数的质数
• 分解质因数，即一个大于1的数一定可以由多个相同或不同的质数相乘得到，我们即寻找这些质数

  例题

  https://www.acwing.com/problem/content/869/

  ACcode

  #include <iostream>
  using namespace std;
  
  int n, x;
  
  int main()
  {
      cin >> n;
      while(n --)
      {
          cin >> x;
          for (int i = 2; i <= n / i; i ++)
          {
              if(x % i == 0){
                  int s = 0;
                  while(x % i == 0)
                  {
                      s ++;
                      x /= i;
                  }
                  cout << i << " " << s << endl;
              }
          }
          if(x > 1) cout << x << " " << 1 << endl;
          cout << endl;
      }
      return 0;
  }

  筛质数

1.朴素筛法(nloglogn)

有2~n这些数，我们从前向后依次筛去当前数的倍数

核心代码

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

2.线性筛法(O(N))

核心思想：n只会被最小质因子筛去

(1) i % pj == 0
pj一定是i的最小质因子，pj一定是pj*i的最小质因子
(2) i % pj != 0
pj 一定小于i的所有质因子,pj也一定是pj*i的最小质因子

核心代码

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}