[数论]-----欧拉筛法的应用
求文章目录1.1~n之间所有素数求2.1~n之间所有自然数的欧拉函数(x )求3.1~n之间每个数的因子个数并详细推导：代码： 4.1~n之间的每个数的因子和详细推导：代码：担心筛法的马修
欧拉法的核心思想：每个因子只能根据自己的最小质量因子筛选一次
求出2.1~n之间所有自然数的欧拉函数(x )，求出3.1~n之间的每个数的因子的个数并详细导出。 代码： void Euler () memset ) isprime，1，sizeof isprime )； d[1]=1； for(intI=2； i=n； I ) if(isprime[I] ) {prime[ tot]=i； d[i]=2； num[i]=1； }for(intj=1； j=toti*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； 布雷克； }else{d[i*prime[j]]=d[i]*2； num[i*prime[j]]=1； } }求出}}4.1~n之间各数据的因数和详细导出：
代码： o(n ) )。
void Euler () { ans[1]=1； for(LLI=2； i=r； I ) if (！ vis[I]}{prime[CNT]=I； s[i]=psum[i]=i 1； //i为素数vis[i]=1； }for(llj=1； j=cntprime[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 ]； 布雷克； } else { psum [ I * prime [ j ] ]=prime [ j ] 1； s[i*prime[j]]=s[i]*s[prime[j]]； } }求筛法担忧的棉花糖函数