基础数论二：分解质因数、筛质数

1.分解质因数

? ? ?什么是质因数？质因数（素因数或质因子）在数论里是指能整除给定正整数的质数

? ??正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式?。只有一个质因子的正整数为质数。

? ? ?分解质因数只针对合数(分解质因数也称分解素因数)，求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法，和除法的性质相似，所以有如下代码：

void divide(int x)
{
   for(int i=2;i<=x;i++)
   {
      if(x%i==0)//i一定是质数
      {
         int s=0;
         while(x%i==0)
         {
           x/=i;
           s++;
         }
          cout<<i<<' '<<s<<endl;
   }
   if(x>1)cout<<x<<' '<<1<<endl;
}

? ? ?为什么这里i一定是质数呢，为什么这种方法可行呢?

? ? ?我们先判断x%i是否等于0，如果等于0，说明i是x的因子，我们要把i这个因子给去掉，就要进入循环，只要x%i==0成立，我们就执行x/=i的操作，把所有含i的因子给筛掉，这样在下次的时候，x中就不含2~i-1的所有因子，又因为i能整除x，则i也不含2~i-1的因子。

例题

#include <iostream>
#include <algorithm>
using namespace std;
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;//s为指数
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}

2.筛质数

? ? ?我们想知道1~100有多少质数，怎么办呢？这就是筛选质数的问题，前面我们讲到试除法判定质数，我们这里可以设置循环，循环判断x是否为质数，但显然这样时间方面是不太可观的，下面讲两种筛质数的方法

2.1 埃拉托斯特尼筛法(埃氏筛法)

? ? ?埃氏筛法基本思路是：首先将2到n范围内的整数写下来，其中2是最小的质数，将表中所有的2的倍数的数划掉，然后就是3，3是质数，把表中所有3的倍数的数划掉.....依次类推，如果表中剩余的最小的数是n，那么n就是质数，然后再把表中所有m的倍数的数划去，反复进行，就能筛出2到n的所有质数。

const int N = 100010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
          primes[cnt ++ ] = i;
          for (int j = i + i; j <= n; j += i)st[j] = true;
        }
    }
}

? ? ? st[]用来判断遍历到的数是否被划掉，如果st[i]=false，说明i是i到n最小的质数，添加到primes中，然后就把所有i的倍数的数划掉，令st[j]=true，来说明j已经1被划掉；如果st[i]=true，则说明i已经被划掉，不会执行任何

例题：

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;
bool st[N];

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

int main()
{
    int n;
    cin >> n;
    
    get_primes(n);
    
    cout << cnt << endl;
    
    return 0;
}

?2.2 线性筛法

? ? ? 埃氏筛法的问题就在于同一个合数可能会被筛多次，当i=4时，数组中元素2和3会把12筛掉；当i=6的时候，数组中元素2、3再次把12筛掉，如果数据很大的情况下，这种多余的操作我们是承受不住的，那有没有只筛一次的算法呢？线性筛闪亮登场，先看是如何实现的：

int prime[N],cnt;
bool st[N];

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

? ? ? ?这是怎么做到只筛一次的？首先还是判断i是否被筛过，如果没有就存储到prime数组中，接下来就是线性筛的核心，线性筛的核心就是保证每个合数是被它的最小质因子筛掉的，因为我们是从2~n进行遍历，所以我们对于任意的i，先对j=0开始的prime数组进行遍历，st[prime[j]*i]=true；这样就把prime[j]这个最小质因子的i倍的数给筛掉了，那之后怎么保证只筛一次呢？if(i%prime[j]==0)break这段代码就起了巨大的作用，prime数组中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定也可以被 prime[j] 筛掉，因为i中含有prime[j], prime[j] 比 prime[j+1] 小。

? ? ? ?什么意思呢？举个例子，比如30=3*10=2*15，如果我们使用埃氏筛法会筛两次，但我们使用线性筛法就不会，当i=10时，prime[0]=2，此时i%prime[j]==0，后面我们就不能再执行了，因为i*prime[j+1]=10*3=5*2*3能被prime[j]=2给筛掉，因为i的因子是包含prime[j]的，此后的所有合数都能被prime[j]这个最小质因子筛掉，我们就不能再使用其他质因子进行筛除，否则就会重复筛。

? ? ? 对于线性筛的理解还不是很深刻，有想的特别明白的可以评论哦。