质数

定义：在大于$1$的自然数中，除了$1$和它本身不再有其他因数的自然数。

质数的判定(试除法)：

• 暴力枚举，时间复杂度$O(n)$

bool is_prime(int n)
{
    if(n < 2) return false;
    for(int i = 2; i <= n; i ++ )
        if(n % i == 0)
            return false;
    return true;
}

• 优化，时间复杂度：妥妥的$O(\sqrt{n})$

优化的理由：如果一个数$ \ a \ $能够被$ \ n \ $整除，那么假设$ \ b \ = \ n \ / \ a \ \ (b>a) \ $也一定能够被$n$整除。

举个例子：假设$ \ a = 3\ ,n = 12 $ 。此时$ \ 3 \ $ 能够被 $ \ 12 \ $ 整除，$ \ b \ = \ 12 \ / \ 3 \ = \ 4 \ $也能被$ \ 12 \ $整除

这样我们就可以只枚举较小部分从而判断$ \ n \ $是不是质数了

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

// 注意for循环的时候不能写成一下两种情况：
// ①for(int i = 2; i * i <= n; i ++ ) 
// i * i 可能爆long long
//
// ②for(int i = 2; i <= sqrt(n); i ++ ) 
// 每次都会计算sqrt()很耗时间

分解质因数(试除法):

• 暴力枚举 从小到大一直枚举到$ \ n \ $，判断当前的数是不是 $ \ n \ $的质因数。时间复杂度$O(n)$

void divide(int x)
{
    for(int i = 2; i <= n; i ++ )
        if(x % i == 0)
        {
            int cnt = 0;  // cnt用于记录当前满足要求的i(质因数)出现了几次
            while(x % i == 0)  // 如果能整除
            {
                x /= i;  // 对x整除i
                cnt ++ ;  // i出现的次数加1
            }

            cout << i << " " << cnt << endl;
        }
}

有个小提问？！这样分解质因数会不会出现合数(质数的对立面，最小的合数为4)呢？

答案是不会的！因为当分解一个质数$ \ i \ $的时候，这个算法会把$[i + 1, n]$中所有的与质数$ \ i \ $相关的倍数全部筛掉。就比如说当$ \ i=2 \ , n=12 \ $的时候，通过$while$循环，使得$ \ n = 12 / 2=6，n = 6 / 2 = 3 \ $此时2的倍数

4(合数)就会被除干净。

• 优化，时间复杂度：平均$O(\sqrt{n})$

因为$\color{#FF0000}{n中只包含一个大于\sqrt{n}的数}$。

证明：

假设有两个大于$\sqrt{n}$的数$ \ a, \ b \ $，那么$ \ a \ * \ b \ > \ \sqrt{n} \ * \ \sqrt{n} \ = n $ ，就矛盾了。

void divide(int x)
{
    for(int i = 2; i <= n / i; i ++ )
        if(x % i == 0)
        {
            int cnt = 0;
            while(x % i == 0)
            {
                x /= i;
                cnt ++ ;
            }

            cout << i << " " << cnt << endl;
        }
    if(x > 1) cout << x << " " << 1 << endl;  // 处理大于sqrt(x)的那一个数
}

筛质数（素数）

• 暴力枚举 如果当前的数$ \ i \ $没有被筛过的话就加入$primes$数组中，然后将$[i + 1, \ n]$中所有是$ \ i \ $的倍数的数筛掉，因为$ \ i \ $一定是它的一个质因子，时间复杂度$O(nlogn)$

int primes[N], cnt;  // primes: 用于记录1 ~ n中所有的素数，cnt: 用于记录素数的个数
bool st[N];  // 判断当前数是否被前面的数筛过了

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++ )
    {
        if(!st[i]) primes[cnt ++ ] = i;  // 如果当前的数没有被筛过，则加入primes数组中

        for(int j = i + i; j <= n; j += i) st[j] = true;  // 将所有i的倍数的数都筛掉
    }
}

• 优化（埃氏筛法），在筛素数的时候，我们只需要将所有素数的倍数筛掉即可。就比如说先筛掉2的倍数，然后到筛掉4的倍数，会发现4的倍数已经被2的倍数筛掉了，如果按照上面的算法会进行重复操作。时间复杂度$ \ O[nlog(logn)] \ $近似等于 $ \ O(n) \ $。

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;  
        }
    }
}

• 优化（线性筛法），n只会被最小质因子筛掉

借鉴了题解第一的佬的思路

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 = 0; primes[j] <= n / i; j ++ )  // primes[j] <= n / i:变形一下得到
                                                   // primes[j] * i <= n,把大于n的合数都筛了就没啥意义了
        {
            st[primes[j] * i] = true;  // 用最小质因子去筛合数

            // 1)当i % primes[j] != 0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j] < i的
            // 最小质因子,所以primes[j] * i的最小质因子就是primes[j];
            // 2)当有i % primes[j] == 0时,说明i的最小质因子是primes[j],因此primes[j] * i的最小质因子也就应该是
            // prime[j]，之后接着用st[primes[j+1] * i] = true去筛合数时，就不是用最小质因子去更新了,因为i有最小
            // 质因子primes[j] < primes[j + 1],此时的primes[j + 1]不是primes[j + 1] * i的最小质因子，此时就应该
            // 退出循环，避免之后重复进行筛选。

            if(i % primes[j] == 0) break;
        }
    }
}