关于算法:欧拉函数求小于等于n且与n互质的数的个数

39次阅读

共计 1412 个字符，预计需要花费 4 分钟才能阅读完成。

互质：两个数互质代表两者最大公约数为 1
最大公约数求法：辗转相除法，最小公倍数：较大值除以最大公约数乘以较小值

辗转相除法：

较大的数 a 取模较小的数 b，得取模值 c
若取模值等于 0 则最大公约数为取模值，否则持续下一步

a 与 c 再次取模，回到第二步

// 求最大公约数 gcd 以及最大公倍数 lcm
 // 36 24 36/24
 // 24 12 24/12
 // 0 完结最大公约数为 12
 // 求最小公倍数
 // lcm(a, b) = (a * b)/gcd(a, b)
 public static int gcd(int a, int b){
  //a>=b
  // 辗转相除法
  if (b==0){return a;}
  return gcd(b,a%b);
 }

穷举到 n，一一判断该数与 n 的最大公约数是否为 1，即是否为互质

论断：能够实现，但工夫复杂度太高

在数论，对正整数 n，欧拉函数是小于等于 n 的正整数中与 n 互质的数的数目.

n 为正整数 n，p1、p2 ……pn 为正整数 n 的质因数

n 的质因数：既是 n 的因数，又是质数的数

计算方法：

$$
\phi (n) = n \times (\frac{p_1-1}{p_1})\times (\frac{p_2-1}{p_2})\cdots\times (\frac{p_n-1}{p_n})
$$

例：

$$
\phi (10) = 10 \times \frac{1}{2}\times \frac{4}{5} = 4
$$

质数的求法：因数只有 1 和其自身
1. 单个质数 n 的判断
  
  顺次判断 2 到的数被 n 取模的值是否等于零，存在任意一个即不为质数
  
  当 p 大于时，代表数 p 肯定能够失去一个小于的数和一个大于的成对因数，不为质数
2. 从 2 到 n 的质数的判断
  
  非穷举，穷举工夫复杂度为 O(n)，应用素数筛法为 O()
  
  为保障效率，质数为 false，合数为 true
  1. 标记 2 到 n 的数都为质数，为 false，布尔数组默认值为 false，无需再一一标记
  2. 从 2 开始标记数，找到第一个为 false 的数 p
  3. 标记数 p 的倍数为合数，即为 true，倍数标记从 p p 开始，直至数 p 等于，完结标记
    
    起因：
    
    p 的倍数的因数必有 p，不合乎质数条件，每次从 pp 开始标记是因为 p - 1 的局部曾经进行了标记，不再反复标记，

4) 使得下一个数 p 为未被标记为合数的数，即数值仍为 333333false 的数，反复第三步

5) 将标记为 false 的，即为质数的全副输入

采取素数筛法求取质数时，可将倍数标记的操作批改为乘以(1-1/p)，使得每一个数都能乘以其质因数

顺次存入数组中，最初对立顺次输入后果。

public static int f1(int n){
     int res = n;
     for (int i = 2;i*i<=n;i++){if (n % i==0){res = res / i*(i-1);//res/i
             while (n % i == 0){n/=i;}
         }
     }
     if (n>1){res = res/n*(n-1);
     }
     return res;
 }
 // 区间内欧拉函数取值
 public static int[] f2(int n){int[] count = new int[n+1];
     for (int i = 1;i <= n;i++){count[i]=i;
     }
     for (int i =2 ;i <= n;i++){if (count[i] == i){for (int j = i;j <= n;j+=i){count[j] = count[j]/i*(i-1);
             }
         }
     }
     return count;
 }