for(re i=1;i<=n;++i)
	{
		int tmp=i,pos=1;
		while(1)
		{
			while(tmp%prime[pos]==0) 
				cnt[prime[pos]]++,tmp/=prime[pos];
			if(prime[++pos]>tmp)break;
		}
	}

$prime[\text{ }]$ 里面装的是质数表。