線性篩法求歐拉函數與素數表：O(n) 時間預處理 GCD 為素數的數對計數

問題轉化

求 1 ≤ x, y ≤ N 且 gcd(x, y) 為素數的有序數對個數。
令 g = gcd(x, y) 為素數 p，則 x = p·x', y = p·y' 且 gcd(x', y') = 1，其中 1 ≤ x', y' ≤ N/p。
故答案為 Σ_{p prime} ( 2·Φ(N/p) - 1 )，其中 Φ(k) = Σ_{i=1}^k φ(i) 為前綴和，φ 為歐拉函數。減 1 是因 (p, p) 被雙向計算一次。

線性篩同時求 φ 與素數表

const int MAXN = 10000010;
int n, primes[700000], pcnt;
long long phi[MAXN];

void linear_sieve() {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!phi[i]) { primes[pcnt++] = i; phi[i] = i - 1; }
        for (int j = 0; j < pcnt && i * primes[j] <= n; ++j) {
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            } else {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
        }
    }
    for (int i = 2; i <= n; ++i) phi[i] += phi[i-1]; // 前綴和 Φ
}

主程序

int main() {
    scanf("%d", &n);
    linear_sieve();
    long long ans = 0;
    for (int i = 0; i < pcnt && primes[i] <= n; ++i)
        ans += (phi[n / primes[i]] << 1) - 1;
    printf("%lld\n", ans);
    return 0;
}

複雜度分析

• 線性篩：O(n) 時間，O(n) 空間；
• 枚舉素數求和：O(π(n))；
• N ≤ 10⁷ 時記憶體約 80 MB，時間 < 1s（C++ 優化編譯）。

關鍵點

• 線性篩核心：每個合數僅被其最小質因子篩一次，保證 O(n)；
• φ 遞推公式：p ∤ i ⇒ φ(ip) = φ(i)·(p-1)；p | i ⇒ φ(ip) = φ(i)·p；
• 前綴和轉換後直接 O(1) 查詢區間互質對數。