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;
}