欧拉函数：
就是对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。
欧拉函数的通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)
所以，根据通式我们可以打出以下代码：
ll eular(ll n) {
ll ans = n; for(int i=2; i*i <= n; ++i) {
if(n%i == 0) {
ans = ans/i*(i-1); while(n%i == 0) n/=i; } } if(n > 1) ans = ans/n*(n-1); return ans; } 其中，if(n>1)ans-=ans/n; 这个语句是为了保证我们已经除完了n的所有的素因子，有可能还会出现一个我们未除的因子，如果结尾出现n>1 ,说明我们还剩一个素因子木有除。
打表求欧拉函数：
听说这样比较快。。。。
void euler() {
for(int i=2;i<maxn;i++){
if(!E[i]) for(int j=i;j<maxn;j+=i){
if(!E[j])E[j]=j; E[j]=E[j]/i*(i-1); } } } 当然，还有百度百科版的：( 欧拉筛素数同时求欧拉函数)
void get_phi() {
int i, j, k; k = 0; for(i = 2; i < maxn; i++) {
if(is_prime[i] == false) {
prime[k++] = i; phi[i] = i-1; } for(j = 0; j<k && i*prime[j]<maxn; j++) {
is_prime[ i*prime[j] ] = true; if(i%prime[j] == 0) {
phi[ i*prime[j] ] = phi[i] * prime[j]; break; } else {
phi[ i*prime[j] ] = phi[i] * (prime[j]-1); } } } } ② 若i%p==0，有phi（i*p） = p * phi(i)；
④ 当n为奇数时，phi(2n)=phi(n)
⑤ 若x与p互质，则p-x也与p互质，因此小于p且与p互质的数之和为phi(x)*x/2;
⑥N>1，不大于N且和N互素的所有正整数的和是 1/2 *N *eular(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);
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/199057.html原文链接：https://javaforall.net
