#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int INF = 0x3f3f3f;
int n,a[N],b,c;
int main(){
cin>>n;
for(int i = 1;i<=n;i++){
int m = i;
for(int j = 2;j*j<=m;j++){
while(m%j==0){
a[j]++;
m/=j;
}
}
if(m>1) {a[m]++;}
}
for(int i = 1;i<1e6;i++){
if(a[i]>0) cout<<i<<" "<<a[i]<<endl;
}

}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int n,ans;
int f[N],p[N];
bool v[N];  

void Prime()
{
    v[0]=v[1]=1;
    for(int i=2;i<=n;i++)
	{
        if(!v[i]) 
		{ 
            for(int j=i*2;j<=n;j+=i)
			{ 
                v[j]=1;
            }
        }
    }
    int l=0;
    for(int i=2;i<=n;i++)
	{
        if(!v[i])
        {
        	p[++l]=i;
		}
    }
    return;
}

int main()
{
	cin>>n;
	Prime();
	for(int i=2;i<=n;++i)
	{
		int k=i,s=1;
		for(int j=p[s];k>=j;)
		{
			if(k%j==0)
			{
				f[j]++;
				k/=j;
			}
			else if(v[k]==0)
			{
				f[k]++;
				break;
			}
			else
			{
				j=p[++s];
			}
		}	
	}
	for(int i=2;i<=n;++i)
	{
		if(f[i]>=1)
		{
			printf("%d %d\n",i,f[i]);
		}	
	}
	return 0;
}

C++ :

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=1000010;
int v[maxn];
int prime[maxn],c[maxn];
int m;
void primes(int n){
    m = 0;
    memset(v, 0, sizeof v);
    for(int i = 2; i <= n; i++){
        if(v[i] == 0){
            prime[++m] = i;
            v[i] = i;
        }
        for(int j = 1; j <= m; j++){
            if(prime[j] > v[i] || prime[j] > n / i)
                break;
            v[i*prime[j]] = prime[j];
        }
    }
}
 
void solve(int n){
    int cnt = 0;
    for(int i = 1; i <= m; i++){
        cnt = 0;
        for(ll j = prime[i]; j <=n ; j = j*prime[i])
            cnt += n / j;
        printf("%d %d\n", prime[i], cnt);
    }
}
 
int main()
{
    int n;
    scanf("%d", &n);
    primes(n);
    solve(n);
    return 0;
}