1、B站视频链接：G07 分解质因数 唯一分解定理 试除法_哔哩哔哩_bilibili
题目链接：质因子分解 - 洛谷
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100010];//质因子的个数
void decompose(int x){
for(int i=2;i*i<=x;i++){//i增加，x减少，往中间靠拢
while(x%i==0){
a[i]++;
x/=i;
}
}
if(x>1)a[x]++;
}
int main(){
cin>>n;
for(int i=2;i<=n;i++){
decompose(i);
}
for(int i=1;i<=n;i++){
if(a[i]){
cout<<i<<" "<<a[i]<<endl;
}
}
return 0;
}
![[ZKP] Freivalds’ Algorithm](https://img-blog.csdnimg.cn/direct/8b97fd1e4c2a49249c0c20ee3f089cc0.png#pic_center)
