首页 > 代码库 > 欧拉函数
欧拉函数
void Euler_Sieve_Method(int * euler, int n) { euler[1] = 1; for (int i = 2; i < n; i++) { euler[i] = i; } for (int i = 2; i < n; i++) { if (euler[i] == i) { for (int j = i; j < n; j += i) { euler[j] = euler[j] / i * (i - 1); } } }}
void Euler_Sieve_Method(int * euler, int n):计算欧拉函数1~n的函数值,保存在euler数组中。
欧拉函数的一些性质:
通式:
欧拉定理:对于互质的正整数a和n,有aφ(n) ≡ 1 mod n。
欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)。
设a为N的质因数,若(N % a == 0 && (N / a) % a == 0) 则有E(N)=E(N / a) * a;若(N % a == 0 && (N / a) % a != 0) 则有:E(N) = E(N / a) * (a - 1)。
欧拉函数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。