求1到n的质数个数和O(n)

$\mathcal{AIM}$AIM

我们知道：
对于一个合数$x$x 有$x=p^{a_1}_1*p^{a_2}_2*...*p^{a_n}_n$x=p1a1​​∗p2a2​​∗...∗pnan​​
现在给出一个$n$n 求$x\in[1,n]$x∈[1,n]，所有$x$x分解出的$p$p的幂数和
例如
$n=12$n=12
$2=2^1$2=21
$3=3^1$3=31
$4=2^2$4=22
$5=5^1$5=51
$6=2^1*3^1$6=21∗31
$7=7^1$7=71
$8=2^3$8=23
$9=3^2$9=32
$10=2^1*5^1$10=21∗51
$11=11^1$11=111
$12=2^2*3^1$12=22∗31

数字	个数
2	10
3	5
5	2
7	1
11	1

$\mathcal{Resolvent}$Resolvent

对于一个合数$x$x 有$x=p^{a_1}_1*p^{a_2}_2*...*p^{a_n}_n$x=p1a1​​∗p2a2​​∗...∗pnan​​

$O(n\sqrt n)$O(nn​)

这是最简单的想法，先记录哪些数是质数，再把$n$n以内所有的数分解掉

int cnt;
int prime[maxn],num[maxn];//prime -> 求出来的质数   num -> 每个数出现个数
bool vis[maxn];//欧拉筛里看其是否是质数
ols(n);//这是欧拉筛
for (int i=1;i<=n;++i)
	for (int j=１;j*j<=i&&j<=cnt;++j){
		int t=i;
		while (t%prime[j]==0)	++num[prime[j]],t/=prime[j];
	}

$O(nlog_2n)$O(nlog2​n)

考虑可不可以直接对整体求
这个方法对一些其他题也很有用

int cnt;
int prime[maxn],num[maxn];
bool vis[maxn];
ols(n);
for (int i=1;i<=cnt;++i){
	int t=prime[i],mi=1;//mi -> mi次幂
	while (t<=n){
		num[prime[i]]+=n/t*mi;
		t*=prime[i],++mi;
	}
}

$O(n)$O(n)

对一个数 $x$x
$x/p_1$x/p1​显然是比$x$x小的，若我们知道$x/p_1$x/p1​的答案，那么$x$x的贡献就是$x/p_1$x/p1​的贡献加上对$p_1$p1​的一个贡献
但我们把$x/p_1$x/p1​的答案存下来只会增加复杂度
于是我们可以反过来循环，$x$x先对$p_1$p1​加一个贡献，之后我们就可以认为多了一个$x/p_1$x/p1​了
计算$x/p_1$x/p1​时答案就会多一，显然我们可以一直传递下去，这样每个数只用把自己最小质因子的贡献算出即可

int cnt;
int prime[maxn],num[maxn],come[maxn];//come[i] -> i的最小质因子
bool vis[maxn];
ols(n);
for (int i=n;i>=2;--i){
	if (vis[i]){//如果是个合数
		num[come[i]]+=num[i];//最小质因子加上当前这个数要计算次数
		num[i/come[i]]+=num[i];//加上这个数需计算次数
		num[i]=0;//当前这个数没了
	}
}