1. 试除法判断质数

 //首先，质数是大于等于2的数，1和小于1的数不是质数也不是合数
 #include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int flag;
    while(n--){
        int x;
        cin>>x;
        flag=0;
        if(x==1){
            cout<<"No"<<endl;
        }
        else{
            for(int i=2;i<=x/i;i++){   //注意一下这个地方：
                                    // 因为约数都是成双成对出现的比如12的约数：3和4，d 与 x/d 所以可以不用枚举到X，取一对中
                                    //较小的那个约数，即d<=x/d,所以 d=sqrt(x)
                                    //但是写的时候不要写成i<sqrt(x),这样每次判别会花费很多时间，也不要写成i*i<=x，这样可能
                                    //会出现i*i溢出的情况，最好是写成代码中的形式
                if(x%i==0){
                    cout<<"No"<<endl;
                    flag=1;
                    break;
                }
            }
            if(flag==0)
            cout<<"Yes"<<endl;
        }
    }
    return 0;
}

1. 试除法分解质因数

#include<iostream>
using namespace std;
void divide(int x){
    //为什么说i一定不可能时合数呢，证明如下：
    //假设i是一个合数，那么他一定能分解为质因子，质因子一定在2~i-1内但是这以内的数字在之前已经被除尽了，
    //比如12的质因数是2和3，那么就一定不可能找到6，因为6的质因数是2和3，在这之前已经被除尽了，也就是i一定被
    //x除过了所以i一定不是合数
    for(int i=2;i<=x/i;i++){ //小于sqrt(n)的质因子
    //n中只包含一个大于sqrt(n)的质因子，因为如果有两个大于sqrt(n)的质因子，那么两这相乘一定大于n这肯定是不成立的
        if(x%i==0){
             int c=0;
            while(x%i==0){
                x/=i;
                c++;
            }
            cout<<i <<' '<<c<<endl;
        }
    }
    if(x!=1){                //这里进行特判如果x有一个大于sqrt(n)的质因子，将他列出
        cout<<x<<' '<<1<<endl;  //这个地方我自己没想到
    }
    cout<<endl;
}
int main(){
    int n;
    cin>>n;
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        divide(x);
    }
    return 0;
}

1. 朴素筛法

i从2开始升序遍历，去掉i的所有小于等于n的倍数，比如：
5以内：
2 3 4 5
2的倍数为4，去掉4，
3的倍数为6，忽略
4的倍数为8，忽略
5的倍数为10，忽略
所以n=5内的质数为2，3，5
所以时间复杂度为n(1/2+1/3+1/4+......+1/n)当n趋于无穷大时，是无穷级数，
时间复杂度为log(nlogn)

#include<iostream>
using namespace std;
const int N=1e6+10;
bool st[N];//没有被筛掉的数也就是质数集合
int primes[N];//存储质数
int main(){
    int n;
    cin>>n;
    int c=0;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[c++]=i;

        }
          for(int j=i+i;j<=n;j+=i){
            st[j]=true;
        }

    }
    cout<<c;

    return 0;
}

1. 埃氏筛法

i从2开始遍历到n的所有质数，然后去掉这些质数的倍数
比如：n=7
2 3 4 5 6 7
从2 开始，筛去4，6
3，筛取6
此时4筛取，跳过
5的倍数10，忽略
6筛掉
7的倍数为14，忽略，
所以质数为2，3，5，7
这种方法与朴素筛法的区别为，朴素筛法是是对每一个元素的倍数进行晒除，
埃氏筛法是将质数的倍数进行筛除，n内有n/lnn个质数，时间复杂度为nloglogn

1. 线性筛法 借鉴的大佬的解答

若 n≈106n≈106，线性筛和埃氏筛的时间效率差不多，若 n≈107n≈107，线性筛会比埃氏筛快了大概一倍。

核心：1∼n1∼n 内的合数 pp 只会被其最小质因子筛掉。（算数基本定理）

原理：1∼n1∼n 之内的任何一个合数一定会被筛掉，而且筛的时候只用最小质因子来筛，然后每一个数都只有一个最小质因子，因此每个数都只会被筛一次，因此线性筛法是线性的。

枚举到 ii 的最小质因子的时候就会停下来，即 if(i % primes[j] == 0) break;

当 i % primes[j] != 0 时，primes[j] 一定小于 ii 的最小质因子，primes[j] 一定是 primes[j]*i 的最小质因子。
当 i % primes[j] == 0 时，primes[j] 一定是 ii 的最小质因子，而 primes[j] 又是 primes[j] 的最小质因子，因此 primes[j] 是 primes[j]*i 的最小质因子。

void get_primes(){
    //外层从2~n迭代，因为这毕竟算的是1~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;
        }
    }

}