sem竞价托管公司,seo的课谁讲的好,shopex网站搬家,重庆短视频seo搜索多少钱[数论]-----欧拉筛法的应用 文章目录1.求1~n之间的所有质数2.求1~n之间所有自然数的欧拉函数φ#xff08;x#xff09;3.求1~n之间的每个数的因子个数详细推导#xff1a;代码#xff1a;4.求1~n之间每个数的因数和详细的推导#xff1a;代码#xff1a;筛法求莫比乌斯函…[数论]-----欧拉筛法的应用
文章目录1.求1~n之间的所有质数2.求1~n之间所有自然数的欧拉函数φx3.求1~n之间的每个数的因子个数详细推导代码4.求1~n之间每个数的因数和详细的推导代码筛法求莫比乌斯函数1.求1~n之间的所有质数
欧拉筛法核心思想每个合数只被自己的最小质因子筛一次
2.求1~n之间所有自然数的欧拉函数φx
3.求1~n之间的每个数的因子个数
详细推导
代码
void Euler(){memset(isprime,1,sizeof isprime); d[1]1;for(int i2;in;i){if(isprime[i]){prime[tot]i;d[i]2;num[i]1;}for(int j1;jtoti*prime[j]n;j){isprime[i*prime[j]]0;if(i%prime[j]0){d[i*prime[j]]d[i]/(num[i]1)*(num[i]2);num[i*prime[j]]num[i]1; break;}else{d[i*prime[j]]d[i]*2;num[i*prime[j]]1;}}}
}4.求1~n之间每个数的因数和
详细的推导 代码
O(n)
void Euler()
{ans[1]1;for(LL i2;ir;i){if(!vis[i]){prime[cnt]i;s[i]psum[i]i1;//i是质数 vis[i]1;}for(LL j1;jcntprime[j]r/i;j){vis[i*prime[j]]1;if(i%prime[j]0){psum[i*prime[j]]psum[i]*prime[j]1;s[i*prime[j]]s[i]/psum[i]*psum[i*prime[j]];break;}else{psum[i*prime[j]]prime[j]1;s[i*prime[j]]s[i]*s[prime[j]];}}}
}筛法求莫比乌斯函数
