素数の個数（Lucy DP）

$S(v, p)$ を「 $2$ 以上 $v$ 以下の整数のうち、素数であるか、最小素因数が $p$ より大きいものの個数」とします。 $S(v, 1) = v - 1$ から始めて $p$ を小さい順に増やすと、 $p$ が素数で $p^2 \le v$ のときだけ $S(v, p) = S(v, p - 1) - (S(\lfloor v / p \rfloor, p - 1) - S(p - 1, p - 1))$ と変わり、 $p^2 > v$ になったところで $S(v, p) = \pi(v)$ になります。 $\lfloor \lfloor N / i \rfloor / p \rfloor = \lfloor N / (ip) \rfloor$ なので、 $v$ は $\lfloor N / i \rfloor$ の形の $O(\sqrt{N})$ 個の値（floor(N/i) の商列挙 を参照）だけを持てば足ります。 $\sqrt{N}$ 以下の $v$ は $v$ を添字に、それより大きい $v = \lfloor N / i \rfloor$ は $i$ を添字にして、2 つのリストで持ちます。

• prime_count(N): $N$ 以下の素数の個数 $\pi(N)$。 $O(N^{3/4} / \log N)$
• prime_sum(N): $N$ 以下の素数の和。同じ DP で、個数の代わりに和を持つ。 $O(N^{3/4} / \log N)$

$N = 10^{11}$ 程度までが目安です。メモリは $O(\sqrt{N})$ です。 $N$ が大きいと prime_sum の値は $2^{63}$ を超えるので、PyPy では少し遅くなります（必要なら途中で mod を取ります）。

例:

print(prime_count(pow(10, 10)))  # 455052511

コード

from math import isqrt


def prime_count(n):
    # n 以下の素数の個数 π(n)（Lucy DP）
    if n < 2:
        return 0
    r = isqrt(n)
    small = [v - 1 for v in range(r + 1)]  # 最後に small[v] = π(v)（v <= r）
    large = [0] + [n // i - 1 for i in range(1, r + 1)]  # 最後に large[i] = π(n // i)
    for p in range(2, r + 1):
        if small[p] == small[p - 1]:
            continue  # p は合成数
        c = small[p - 1]  # p 未満の素数の個数
        m = min(r, n // (p * p))  # n // i >= p^2 となる i の上限
        b = min(m, r // p)  # i * p <= r なら large を、そうでなければ small を見る
        large[1:b + 1] = [large[i] - large[i * p] + c for i in range(1, b + 1)]
        large[b + 1:m + 1] = [large[i] - small[n // (i * p)] + c for i in range(b + 1, m + 1)]
        small[p * p:] = [small[v] - small[v // p] + c for v in range(p * p, r + 1)]
    return large[1]


def prime_sum(n):
    # n 以下の素数の和（prime_count と同じ DP で、個数の代わりに和を持つ）
    if n < 2:
        return 0
    r = isqrt(n)
    small = [v * (v + 1) // 2 - 1 for v in range(r + 1)]
    large = [0] + [(n // i) * (n // i + 1) // 2 - 1 for i in range(1, r + 1)]
    for p in range(2, r + 1):
        if small[p] == small[p - 1]:
            continue
        c = small[p - 1]  # p 未満の素数の和
        m = min(r, n // (p * p))
        b = min(m, r // p)
        large[1:b + 1] = [large[i] - p * (large[i * p] - c) for i in range(1, b + 1)]
        large[b + 1:m + 1] = [large[i] - p * (small[n // (i * p)] - c) for i in range(b + 1, m + 1)]
        small[p * p:] = [small[v] - p * (small[v // p] - c) for v in range(p * p, r + 1)]
    return large[1]