求赞!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll n,cnt,p[N];
bool st[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(ll i=2; i<=n; ++i) {
if(!st[i]) p[++cnt]=i;
for(ll j=1; j<=cnt && i*p[j]<=n; ++j) {
st[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
for(ll i=1; i<=cnt; ++i) {
ll m=n,c=0;
while(m>1) m/=p[i],c+=m;
cout<<p[i]<<" "<<c<<"\n";
}
return 0;
}