线性素数筛选法与欧拉线性筛算法解析

线性素数筛选法与欧拉线性筛算法解析

线性素数筛选法

线性素数筛选法是一种高效找出所有小于给定整数n的素数的方法。其核心思想是利用已经找到的素数来标记非素数，确保每个合数仅被其最小的素因子筛除一次。

int primes[MAXN], marked[MAXN];
void linearSieve()
{
    memset(marked, 0, sizeof(marked));
    int count = 0;
    for (int i = 2; i     {
        if (!marked[i])
            primes[count++] = i;
        for (int j = 0; j         {
            marked[i * primes[j]] = 1;
            if (i % primes[j] == 0)
                break;
        }
    }
}

在上述代码中，marked[i * primes[j]] = 1;表示将当前素数与之前找到的素数的乘积累计标记为非素数。而if (i % primes[j] == 0) break;则确保了每个合数仅被其最小的素因子筛除一次，从而保证了算法的线性时间复杂度。

欧拉线性筛算法

欧拉线性筛不仅能够高效地找出素数，还能同时计算出每个数的欧拉函数值。欧拉函数φ(n)表示小于n的正整数中与n互质的数的数量。

int eulerPhi[N], primes[N], visited[N], primeCount;
void eulerSieve()
{
    for (int i = 2; i     {
        if (!visited[i])
        {
            primes[primeCount++] = i;
            eulerPhi[i] = i - 1;
        }
        for (int j = 0; j         {
            visited[i * primes[j]] = 1;
            if (i % primes[j] == 0)
            {
                eulerPhi[i * primes[j]] = eulerPhi[i] * primes[j];
                break;
            }
            eulerPhi[i * primes[j]] = eulerPhi[i] * (primes[j] - 1);
        }
    }
    eulerPhi[1] = 1; // 特殊情况
}

欧拉函数的计算遵循以下规则：

• 若x为质数，则φ(x) = x - 1。
• 若x % primes[j] == 0，则φ(x * primes[j]) = φ(x) * primes[j]。
• 若x % primes[j] != 0，则φ(x * primes[j]) = φ(x) * (primes[j] - 1)。

这些规则基于欧拉函数的性质，特别是当x和y互质时，φ(xy) = φ(x) * φ(y)。通过这些规则，欧拉线性筛能够在遍历过程中高效地计算出每个数的欧拉函数值。