一、判断单个数是否为质数

• 朴素枚举法：O(n)

bool prime(int x){
    if(x<2) return false;   //特判
    for(int i=2; i<n; i++){ //2到n之间枚举
        if(x%i==0) return false;
    }
    return true;
}

• 优化枚举法：O(sqrt(n))

bool prime(int x){
    if(x<2) return false;   //特判
    //2到sqrt(n)之间枚举，有时候也写成i*i<=n 或者 i<=n/i
    //不建议使用i*i<=n，因为当i比较大时，i*i可能会爆int
    for(int i=2; i<=sqrt(n); i++){ 
        if(x%i==0) return false;
    }
    return true;
}

二、筛法：

• 埃氏筛：质数的倍数一定是合数

const int N=1e8+10;
int n, q, a[N], p[N], cnt=0, x;

void ai(){
    for(int i=2; i<=n; i++){
        if(a[i]==0){
            p[++cnt]=i;

            //将质数的倍数筛掉
            for(int j=i*2; j<=n; j+=i){
                a[j]=1;
            }
        }

    }
}

• 欧拉筛（线性筛）：每个合数只被它的最小质因子筛除一次 O(n)

const int N=1e8+10;
int n, q, a[N], p[N], cnt=0, x;

void oula(){
    for(int i=2; i<=n; i++){
        if(a[i]==0){
            p[++cnt]=i;
        }
        for(int j=1; p[j]<=n/i; j++){
            a[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}

三、分解质因数
给定一个正整数n，对其进行因式分解，如果把所有因子按照非递减顺序排列，其分解形式唯一
n最多只有一个>sqrt(n)的质因子

// 在此处输入您的代码，或加载示例
#include <iostream>
using namespace std;
long long t, x;

void fj(long long x){
    for(long long i=2; i<=x/i; i++){
        while(x%i==0){
            printf("%lld ", i);    
            x/=i;            
        }
    }
    if(x>1) printf("%lld", x);
    printf("\n");
}

int main(){      
    scanf("%lld", &t);  
    while(t--){
        scanf("%lld", &x);
        fj(x);
    }

    return 0;
}