质数

判定是否是质因数：试除法

• 通过数学定义判断余数是否等于0即可
• 时间复杂度 o(n)
• 优化
  （1）如果如果一个数可用被整除，结果是成双成对的，所以只要枚举到d和n/d较小的一个，所以d<=n/d,d<=sqrt(n)。判断条件有三种写法：1）i <= n/i;2）i <= sqrt(n);3）i * i <= n;推荐写第一种，第二种比较慢，第三种写法i*i可能会溢出。优化后的时间复杂度为o(sqrt(n))。
  （2）代码

#include <stdio.h>
#include<iostream>
using namespace std;

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;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a;
        cin>>a;
        if(is_prime(a)) printf("Yes\n");
        else printf("No\n");
    }
}

分解质因数

• 从小到大枚举所有数，首先判断是否是和数。
• 如果是和数，通过除以一个数来分解和数，同时要统计次数。
• 不用担心除以的数不是质数，因为除以的数是从小到大来的，所以这个和数肯定有更小的质因子，并在之前除过了。
• n中最多只有一个大于sqrt(n)的质因子，如果两个质因子都大于sqrt(n)，那么乘积大于n了。所以最后单独处理一下。
• 时间复杂度是o(logn)~o(sqrt(n))假设x是2的k次方，在while循环那一步直接能除完，for循环就不用继续了。
• 代码：

#include<iostream>
using namespace std;

void divide(int x){
    for(int i = 2; i <= x/i; i++){
        if(x % i == 0){
            int s = 0;
            while(x % i == 0){
                x = x/i;
                s++;
            }
            cout<<i<<' '<<s<<'\n';
        }
    }
    if(x > 1) cout<<x<<' '<<'1'<<'\n';
    cout<<'\n';
    return ;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        int a;
        cin>>a;
        divide(a);
    }
    return 0;
}

计算质数个数

最朴素的筛法：

• 首先用一个数组记录质数。
• 再用当前数，把它的倍数筛掉。
• 时间复杂度o(nlogn)
• 代码：

void prime_num(int x){
    int cnt = 0;
    for(int i = 2; i <= x; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = i; j <= x; j+=i) st[j] = 1;//无论是质数还是合数，都用来筛掉后面的数。
    }
    cout<<cnt;
}

埃氏筛法

• 首先用一个数组记录质数。
• 只用质数，把它的倍数筛掉。
• 时间复杂度o(nloglogn)
• 代码：

void prime_num(int x){
    int cnt = 0;
    for(int i = 2; i <= x; i++){
        if(!st[i]){
             primes[cnt++] = i;
             for(int j = i; j <= x; j+=i) st[j] = 1;//只用质数来筛掉后面的数
        }
    }
    cout<<cnt;
}

线性筛法