首页 > 代码库 > 欧拉筛素数+求欧拉函数
欧拉筛素数+求欧拉函数
线性筛法
prime记录素数，num_prime素数下标
它们保证每个合数只会被它的最小质因数筛去
a[0]=a[1]=1; for(int i=2;i<=n;i++) { if(!a[i]) prime[num_prime++]=i; for(int j=0;j<num_prime&&i*prime[j]<=n;j++) { a[i*prime[j]]=1; if(!(i%prime[j])) break; } }}
欧拉函数
是
积性函数：对于任意互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。
通式： 
其中p1, p2……pn为x的所有质因数，x是不为0的整数。
φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。
注意：每种质因数只一个。 比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4
若n是质数p的k次幂， 
，因为除了p的倍数外，其他数都跟n互质。
设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值
φ：N→N，n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质， 
特殊性质：当n为奇数时， 
, 证明与上述类似。
若n为质数则 
#include<cstdio>#include<cstring>#define MAXN 100005#define MAXL 1299710int prime[MAXN];int check[MAXL];int phi[MAXL];int tot = 0;phi[1] = 1;memset(check, 0, sizeof(check));for (int i = 2; i < MAXL; ++i){ if (!check[i]) { prime[tot++] = i; phi[i] = i - 1; } for (int j = 0; j < tot; ++j) { if (i * prime[j] > MAXL) { break; } check[i*prime[j]] = 1; if (i % prime[j] == 0) { phi[i*prime[j]] = phi[i] * prime[j]; break; }else { phi[i*prime[j]] = phi[i] * (prime[j]-1); } }}
欧拉筛素数+求欧拉函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。