Problem 954: Prime Counting Function

Mathematical Analysis

The Prime Counting Function

The prime counting function $\pi(x)$ gives the number of primes $p \le x$. By the Prime Number Theorem (proved independently by Hadamard and de la Vallee Poussin in 1896):

A better approximation is the logarithmic integral: $\pi(x) \approx \operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t}$.

Estimating the Sum

We need $\pi(k^2)$ for $k = 1, \ldots, 10^4$, so the largest argument is $(10^4)^2 = 10^8$. By PNT:

The sum is approximately:

For $N = 10^4$: $\frac{10^{12}}{6 \cdot 4 \ln 10} \approx 1.8 \times 10^{10}$, which is in the right ballpark.

Prefix Sum Approach

Theorem (Prefix Sum Method). If $P[n] = \sum_{j=2}^{n} \mathbf{1}[\text{j is prime}]$ is the prefix sum of the prime indicator, then $\pi(n) = P[n]$ for all $n \ge 2$, and the desired sum is $\sum_{k=1}^{N} P[k^2]$.

This allows us to compute all required values with a single sieve followed by $O(N)$ lookups.

Concrete Examples

Partial sums: $\sum_{k=1}^{10} \pi(k^2) = 0 + 2 + 4 + 6 + 9 + 8 + 15 + 18 + 21 + 25 = 108$. Wait, let me be precise: $\pi(36)=11, \pi(49)=15, \pi(64)=18, \pi(81)=22$.

Derivation

Editorial

Compute sum_{k=1}^{10^4} pi(k^2) where pi(x) is the prime counting function. Algorithm: 1. Sieve of Eratosthenes up to (10^4)^2 = 10^8 2. Build prefix sum of prime indicator 3. Sum pi(k^2) for k = 1, …, 10^4 Complexity: O(M log log M) time, O(M) space, M = 10^8. We sieve of Eratosthenes** up to $M = (10^4)^2 = 10^8$. Finally, build prefix sum** array: $P[n] = P[n-1] + [n \text{ is prime}]$ for $n = 2, \ldots, M$.

Pseudocode

Sieve of Eratosthenes** up to $M = (10^4)^2 = 10^8$
Build prefix sum** array: $P[n] = P[n-1] + [n \text{ is prime}]$ for $n = 2, \ldots, M$
Accumulate** $S = \sum_{k=1}^{10^4} P[k^2]$

Memory Optimization

A boolean sieve for $10^8$ entries requires 100 MB. Using a bitset reduces this to ~12.5 MB. Alternatively, a segmented sieve can be used with $O(\sqrt{M})$ memory, though the prefix-sum approach requires storing cumulative counts.

Verification

Cross-check with known values: $\pi(10^8) = 5761455$ (well-established). The sum of the first few terms can be verified manually.

Proof of Correctness

Theorem. The Sieve of Eratosthenes correctly identifies all primes up to $M$.

Proof. If $n \le M$ is composite, then $n = ab$ with $1 < a \le b$, so $a \le \sqrt{M}$. The sieve marks $n$ as composite when processing the smallest prime factor of $n$, which is $\le a \le \sqrt{M}$. Hence every composite number is correctly identified. $\square$

Corollary. The prefix sum $P[n]$ equals $\pi(n)$ for all $1 \le n \le M$.

Complexity Analysis

• Sieve: $O(M \log \log M)$ time, $O(M)$ space (or $O(M / 8)$ with bitset).
• Prefix sum: $O(M)$ time.
• Final summation: $O(\sqrt{M})$ time.
• Total: $O(M \log \log M)$ with $M = 10^8$.

Answer

/*
 * Problem 954: Prime Counting Function
 *
 * Compute sum_{k=1}^{10^4} pi(k^2).
 *
 * Algorithm:
 *   1. Sieve primes up to (10^4)^2 = 10^8
 *   2. Build prefix sum array of prime indicator
 *   3. Sum pi(k^2) for k = 1 to 10^4
 *
 * Complexity: O(M log log M), M = 10^8.
 * Memory: ~100 MB for boolean sieve + prefix sums.
 */

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int N = 10000;
    const int M = N * N;  // 10^8

    // Sieve of Eratosthenes
    vector<bool> is_prime(M + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; (long long)i * i <= M; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= M; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // Build prefix sum: pi[n] = number of primes <= n
    vector<int> pi(M + 1, 0);
    for (int n = 1; n <= M; n++) {
        pi[n] = pi[n - 1] + (is_prime[n] ? 1 : 0);
    }

    // Sum pi(k^2) for k = 1 to N
    long long total = 0;
    for (int k = 1; k <= N; k++) {
        total += pi[(long long)k * k];
    }

    cout << total << endl;
    return 0;
}

"""
Problem 954: Prime Counting Function

Compute sum_{k=1}^{10^4} pi(k^2) where pi(x) is the prime counting function.

Algorithm:
  1. Sieve of Eratosthenes up to (10^4)^2 = 10^8
  2. Build prefix sum of prime indicator
  3. Sum pi(k^2) for k = 1, ..., 10^4

Complexity: O(M log log M) time, O(M) space, M = 10^8.
"""

from math import isqrt, log

def sieve_prefix(M: int) -> list[int]:
    """Compute prefix sum of prime indicator up to M.

    Returns array P where P[n] = number of primes <= n.
    """
    is_prime = bytearray(b'\x01') * (M + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, isqrt(M) + 1):
        if is_prime[i]:
            is_prime[i * i::i] = bytearray(len(is_prime[i * i::i]))

    # Build prefix sum in-place
    P = [0] * (M + 1)
    for n in range(1, M + 1):
        P[n] = P[n - 1] + is_prime[n]
    return P

def solve(N: int = 10**4) -> int:
    """Compute sum of pi(k^2) for k = 1 to N."""
    M = N * N
    P = sieve_prefix(M)
    return sum(P[k * k] for k in range(1, N + 1))

# --- Compute answer ---
N = 10**4
M = N * N
P = sieve_prefix(M)
answer = sum(P[k * k] for k in range(1, N + 1))

# Verify known values
assert P[100] == 25, f"pi(100) = {P[100]}"
assert P[1000000] == 78498, f"pi(10^6) = {P[1000000]}"

print(answer)