猫史档案馆

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=1e6;
int ga[M+1]={0,1};
void setup_prime_check(){
for(long long i=2;i<=M;i++){
if(!ga[i]){
for(long long j=i;i*j<=M;j++){
ga[i*j]=1;
}
}
}
}
bool is_prime(int n){
return ga[n]==0;
}
const int M2=1e5;
int gcnt[M2+1];
void ff(int n){
for(int i=2;i<=n;i++){
while(n%i==0){
gcnt[i]++;
n/=i;
}
if(is_prime(n)){
gcnt[n]++;
break;
}else if(n==1){
break;
}
}
}
int main(){
int n;
cin>>n;
setup_prime_check();
for(int i=2;i<=n;i++){
ff(i);
}for(int i=2;i<=n;i++){
if(gcnt[i]){
cout<<i<<" "<<gcnt[i]<<endl;
}
}
return 0;
}