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

也许更好的阅读体验
$AIM$AIM

我们知道：
对于一个合数 $x$x 有 $x=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_n^{a_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\ast 3^1$6=21∗31
$7=7^1$7=71
$8=2^3$8=23
$9=3^2$9=32
$10=2^1\ast 5^1$10=21∗51
$11=11^1$11=111
$12=2^2\ast 3^1$12=22∗31

$Resolvent$Resolvent

对于一个合数 $x$x 有 $x=p_1^{a_1}\ast p_2^{a_2}\ast ...\ast p_n^{a_n}$x=p1a1​​∗p2a2​​∗...∗pnan​​

$O\left(n\sqrt{n}\right)$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\left(nlo{g}_{2}n\right)$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\left(n\right)$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;//当前这个数没了
	}
}