1. 埃拉托斯特尼筛法（埃氏筛）
在埃氏筛中，数组mk[i] = true表示数字i是非素数。该算法的时间复杂度通常被认为是O(n log log n)。在实现时，内层循环可以从i*i开始，而不是i*2，因为i*2, i*3, ..., i*(i-1)这些数字已经在之前的迭代中被处理过。这样可以减少不必要的计算，提高效率。
1 mk[1] = true;
2 for (int i = 2; i <= N; ++i) {
3 if (mk[i]) continue;
4 for (int j = i * i; j <= N; j += i) mk[j] = true;
5 }
2. 欧拉筛法
欧拉筛法是一种线性时间复杂度O(n)的素数筛选方法，因为它确保每个合数仅被其最小的质因数筛除一次。这使得欧拉筛比埃氏筛更为高效。
1 void euler(int mx) {
2 int i, j, cnt = 0;
3 for (i = 2; i <= mx; ++i) {
4 if (!mark[i]) {
5 primes[cnt++] = i;
6 phi[i] = i - 1;
7 }
8 for (j = 0; j
10 if (i % primes[j] == 0) {
11 phi[i * primes[j]] = phi[i] * primes[j];
12 break;
13 }
14 phi[i * primes[j]] = phi[i] * (primes[j] - 1);
15 }
16 }
17 }
3. 计算单个欧拉函数值
欧拉函数φ(n)用于计算小于n且与n互质的正整数的数量。下面是一个计算单个φ(n)值的函数实现。
1 int phi(int v) {
2 if (v == 1) return 1;
3 int ans = v;
4 for (int i = 2; i * i <= v; ++i) {
5 if (v % i == 0) {
6 ans -= ans / i;
7 while (v % i == 0) v /= i;
8 }
9 }
10 if (v > 1) ans -= ans / v;
11 return ans;
12 }
![python的交互模式怎么输出名文汉字[python常见问题]](https://img1.php1.cn/3cd4a/24cea/978/9f39a0b333a15215.gif)
京公网安备 11010802041100号