筛法求欧拉函数c++

筛法求欧拉函数是一种用于计算小于一定界限n的所有正整数的欧拉函数φ(n)的高效算法。在C++中，常用的是埃拉托斯特尼筛法（Sieve of Eratosthenes），步骤如下：

1. 创建一个大小为n+1的布尔型数组isPrime，初始化所有元素为true，表示从0到n都是质数。
2. 遍历从2到√n，对于每个质数p：
a. 如果isPrime[p]为true，说明p是质数，则将它的倍数p*i（i从p开始，每次加1直到n）标记为合数，即isPrime[p*i]设为false。这是因为除了本身以外，任何大于1的数都能分解成若干个质因数的乘积，如果其中一个质因数已经在之前的遍历中处理过了，那么这个倍数就不再是质数。
3. 计算欧拉函数值：对于每一个数字i（i > 1），若isPrime[i]为true，表明i没有除1和它自身外的其他因子，所以φ(i) = i - 1。否则，φ(i) = p * (i / p)，其中p是i的最小非平凡质因数。

以下是简单的C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

int phi(int n) {
    vector<bool> isPrime(n + 1, true);
    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    int result = n;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i])
            result -= result / i;
    }
    return result;
}

int main() {
    int n;
    cout << "请输入一个整数: ";
    cin >> n;
    cout << "欧拉函数φ(" << n << ") 的值是: " << phi(n) << endl;
    return 0;
}