题解

用桶记录每一个因子就行

#include <iostream>
#include <cstdio>
using namespace std;
int bucket[100005];
void luru(int x){
	for(int i = 2; i * i <= x; i++){
		while(x % i == 0){
			bucket[i]++;
			x /= i;
		}
	}bucket[x]++;
}
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		luru(i);
	}for(int i = 2; i <= 10000; i++){
		if(bucket[i]) printf("%d %d\n", i, bucket[i]);
	}

	return 0;
}

时间复杂度：$O(n\sqrt{n})$