试除法判定质数

一、质数

1.质数概念：

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

2.质数的判定——试除法

(1)朴素试除法

遍历从​2到​n-1的所有数字，只要其中有​n的约数，就不符合质数的概念，则返回 false。
示例代码：

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

• 质数必须大于等于2
• 时间复杂度为​O(n)

(2)优化试除法

首先我们先来了解一个性质：如果​d能够整除​n，则​\frac{n}{d}一定也能整除​n，所以在每次约数的时候，我们就发现了​d与​\frac{n}{d}都是成双成对出现的，所以我们只需要枚举较小的那一个就可以了。因此枚举的条件就是​d\leq\frac{n}{d}，简单化简一下就是​d^{2}\leq n，​d\leq \sqrt{n}。因此，我们在循环的时候只需要枚举到​\sqrt{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;
}

• 对于循环的结束条件，如果写成 i * i <= n会有溢出的风险
• 对于循环的结束条件，如果写成 i <= sqrt(n)会大大增加时间复杂度，因为每次都要重新取。
• 时间复杂度为​O(\sqrt{n})

3.分解质因数

(1)朴素算法

从小到大枚举所有的数，如果发现某个数字​t可以被整除，那么就循环求有多少个​t可以被整除，直到无法被整除。
示例代码：

void divide(int 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 << "\n";
        }
    }
}

有读者可能会有疑问：为什么分解质因数枚举的不是质数，而是自然数呢？其实仔细一思考就能得到答案，当我们枚举到每个i的时候，就意味着我们n已经不包含任何从​2到​i-1的质因子了，而​i如果是合数的话，必然包含​2到​n-1的质因子一定也是质数了。

(2)优化算法

我们首先了解一个很重要的性质：​n中最多只包含一个大于​sqrt{n}的质因子。怎么证明的呢？假设有两个大于​sqrt{n}的质因子，那么相乘一定大于​n。
所以我们枚举的时候，可以先将所有小于等于​sqrt{n}的质因子枚举出来，然后最后如果 n>1，说明最后剩下的数字一定是那个大于​sqrt{n}

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 << "\n";
        }
    }
    if(n > 1) cout << n << "1\n";
    cout << endl;
}

• 时间复杂度为​O(sqrt{n})

4、质数的判定——埃氏筛法

对于每个枚举到的​t，他的任何倍数就一定是合数而非质数。所以我们可以在每次枚举到质数的时候，标记范围内它的所有倍数，这样就可以节省相当多的时间了。

示例代码：

int primes[N], cnt = 0;
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;
        }
    }
}

时间复杂度分析

首先当​i=2的时候循环了​\frac{n}{2}次，当​i=3的时候循环了​\frac{3}{n}次，以此类推：

​\frac{2}{n}+\frac{3}{n}+\frac{4}{n}+......+\frac{n}{n}=n(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+......+\frac{1}{n})\sim {n\ln n}

1. 括号内​\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}是调和级数​H_n=1+\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n}去掉首项1，即​H_n - 1；
2. 当​n\to\infty（​n趋近于无穷大）时，调和级数的渐近近似为：​H_n \approx \ln n + \gamma（​\gamma\approx0.577，是欧拉常数）；
3. 因此括号内部分取极限的渐近结果：​\frac{1}{2}+\frac{1}{3}+\dots+\frac{1}{n} \approx \ln n + \gamma - 1 \sim \ln

综上所述，大致的时间复杂度就是​O(n\ln n)

---

对于刚才的埃氏筛法，我们做一个简单的优化。我们会发现并不是每一个数的倍数全部都要删除，其实只要删除每个质数的倍数就可以了。举个简单例子，比如​p是质数，那么我们不需要枚举​1～\ p-1的所有数字，只要枚举这个区间之内的质数就可以了。

示例代码：

int primes[N], cnt = 0;
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;
            }
        }
    }
}