#include <cstdio>
#include <vector>
#include <algorithm>

int main(){
    
    std::vector <int> vec;
    int n,tmp,lst,cnt = 1;
    
    scanf("%d",&n);
    for (int i = n;i;i--){
        
        tmp = i;
        for (int j = 2;j * j <= tmp;j++)
            while (tmp % j == 0) 
                tmp /= j,vec.push_back(j);
        if (tmp != 1) vec.push_back(tmp);
        
    }
    std::sort(vec.begin(),vec.end());
    lst = vec[0];
    vec.push_back(-1);
    for (int i = 1;i < vec.size();i++){
        
        if (vec[i] != lst) printf("%d %d\n",lst,cnt),cnt = 1,lst = vec[i];
        else cnt++;
        
    }
    
    return 0;
}

运算量级超1e11竟然好能过（最长604 ms），求加强数据。