主流思路没想到，我太菜了

这里是一个实测比主流解法慢的，弱很多的方法。。。

主流的O(nlogn)比我这个貌似是O(n)快得多（好心人帮我看看复杂度？）

思路：
从线性筛的过程获得启发，一个和数a只会被筛一次，

而且是只是被 a的最小质因子b 乘以 另一个数(a/b) 给筛掉的，

假如我们知道(a/b)的各个质因子的个数，那a的各个质因子的个数是(a/b)的各个质因子的个数，和b这个质因子个数+1。

于是我想到建一棵树，每次筛的时候建边 （a/b） ——> a ，

这样就有了很多棵根为各个质数的树，我们分别统计每棵树的各个数的质因子个数即可。

怎么统计呢？

从根节点开始遍历树，对于最底层的节点y和它的父节点x，

x和y的各个质因子个数是：

2倍的x的各个质因子个数，和y/x这个质因子个数+1，

于是我们可以先累加y/x这个质数+1，2倍的x的各个质因子个数交给x的父节点处理，

对于x的父节点z，只需记z的各个质因子个数和2倍x的各个质因子个数，

即3倍的z的各个质因子个数，和x/z这个质因子个数+2，

以此类推，这就变成了累加数字，读不懂应看看代码。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=(int)1e6+10;
int n;
int prime[maxn],pr;
bool v[maxn];
struct bian
{
    int y,next;
}a[maxn];int last[maxn],len;
void ins(int x,int y)
{
    a[++len].y=y;
    a[len].next=last[x];last[x]=len;
}
void get()
{
    memset(v,true,sizeof(v));pr=0;
    for(int i=2;i<=n;i++)
    {
        if(v[i])prime[++pr]=i;
        for(int j=1;j<=pr&&i<=n/prime[j];j++)
        {
            v[i*prime[j]]=false;
            ins(i,i*prime[j]);
            if(i%prime[j]==0)break;
        }
    }
}
int ans[maxn];
int getans(int x)
{
    if(last[x]==0)return 1;
    int now=1;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        int q=getans(y);
        ans[y/x]+=q;
        now+=q;
    }
    return now;
}
int main()
{
    scanf("%d",&n);
    len=0;memset(last,0,sizeof(last));
    get();
    memset(ans,0,sizeof(ans));
    for(int j=1;j<=pr;j++)ans[prime[j]]+=getans(prime[j]);
    for(int i=1;i<=pr;i++)printf("%d %d\n",prime[i],ans[prime[i]]);
    return 0;
}