問題
整数 $N$ ($N \le 10^{11}$) が与えられる。以下を求めよ:
- $\pi(N)$: $N$ 以下の素数の個数
- $\sum_{p \le N, p \text{ 素数}} p$: $N$ 以下の素数の総和
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 10^{11}$ | 上限が大きい |
| 出力 | 64ビット整数に収まる | 素数和は大きくなりうる |
入出力例
入力例1
100出力例1
25 1060入力例2
1000000000出力例2
50847534 24739512092254535概念図: Lucy_Hedgehog の篩の仕組み
各 $v = \lfloor N/k \rfloor$ のみ管理（高々 $2\sqrt{N}$ 種）。素数 $p$ ごとに合成数を引き算。$O(N^{3/4}/\log N)$ 時間、$O(\sqrt{N})$ 空間。
ヒント
ヒント1（方向性）
$N \le 10^{11}$ ではエラトステネス篩の $O(N \log \log N)$ は無理。Lucy_Hedgehog の篩は $\lfloor N/k \rfloor$ の形の値（高々 $2\sqrt{N}$ 個）のみ管理することで $O(N^{3/4}/\log N)$ を達成する。
ヒント2（アプローチ）
初期: cnt[v] = v-1、sum_[v] = v(v+1)/2-1。各素数 $p \le \sqrt{N}$ について $v \ge p^2$ の全ての管理値 $v$ を更新:
cnt[v] -= cnt[v//p] - cnt[p-1]、sum_[v] -= p*(sum_[v//p] - sum_[p-1])
ヒント3（ほぼ答え）
sqN = int(N**0.5)
# small[i]: cnt/sum_ の値 i (i <= sqN)
# large[i]: cnt/sum_ の値 N//i (i >= 1)
for p in range(2, sqN+1):
if get_cnt(p) == get_cnt(p-1): continue # p は合成数
p2 = p*p
pcnt = get_cnt(p-1); psum = get_sum(p-1)
for v in all_v:
if v < p2: continue
set_cnt(v, get_cnt(v) - (get_cnt(v//p) - pcnt))
set_sum(v, get_sum(v) - p*(get_sum(v//p) - psum))模範解答
import sys
def solve():
N = int(sys.stdin.readline())
if N < 2: print(0, 0); return
sqN = int(N**0.5)
while (sqN+1)*(sqN+1) <= N: sqN+=1
# small[i] = cnt/sum_ for value i (1<=i<=sqN)
# large[i] = cnt/sum_ for value N//i (1<=i<=sqN)
cnt_s = list(range(-1, sqN+1)) # cnt_s[i] = i-1
sum_s = [0]*(sqN+1)
for i in range(1, sqN+1): sum_s[i] = i*(i+1)//2 - 1
m = sqN
cnt_l = [0]*(m+1)
sum_l = [0]*(m+1)
for i in range(1, m+1):
v = N//i
cnt_l[i] = v-1
sum_l[i] = v*(v+1)//2-1
def get_cnt(v):
return cnt_s[v] if v<=sqN else cnt_l[N//v]
def get_sum(v):
return sum_s[v] if v<=sqN else sum_l[N//v]
def set_cnt(v, val):
if v<=sqN: cnt_s[v]=val
else: cnt_l[N//v]=val
def set_sum(v, val):
if v<=sqN: sum_s[v]=val
else: sum_l[N//v]=val
small_v = list(range(2, sqN+1))
large_v = [N//i for i in range(1, sqN+1)]
all_v = large_v + small_v
for p in range(2, sqN+1):
if get_cnt(p) == get_cnt(p-1): continue
p2 = p*p
pcnt = get_cnt(p-1)
psum = get_sum(p-1)
for v in all_v:
if v < p2: continue
set_cnt(v, get_cnt(v) - (get_cnt(v//p) - pcnt))
set_sum(v, get_sum(v) - p*(get_sum(v//p) - psum))
print(get_cnt(N), get_sum(N))
solve()Step-by-Step 解説
Step 1: なぜ $O(N)$ でなく $O(N^{3/4})$ で解けるか
$\lfloor N/k \rfloor$ の形の値は高々 $O(\sqrt{N})$ 種類しかない（$k \le \sqrt{N}$ と $v \le \sqrt{N}$ の二種類）。この値についてのみ篩を管理することで、$O(N^{3/4}/\log N)$ の全体計算量を達成する。
Step 2: 初期化
cnt[v] = v-1（2から$v$までの整数の個数）、sum_[v] = v(v+1)/2-1（その和）。
Step 3: 各素数 p による更新
| 条件 | 操作 |
|---|---|
| $p$ が素数かどうか | cnt[p] != cnt[p-1] を確認 |
| $v \ge p^2$ の各管理値 | cnt[v] -= cnt[v//p] - pcnt |
| （和の更新） | sum_[v] -= p*(sum_[v//p] - psum) |
Step 4: 計算量
$\sqrt{N}$ 個の素数 $p$ に対し、各 $p$ で $O(N/p)$ 個の $v$ を処理するので全体 $O(\sum_{p \le \sqrt{N}} N/p) = O(N^{3/4}/\log N)$。空間は $O(\sqrt{N})$。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
large と small のインデックスを混同 | N//v vs v の参照先が違う | v <= sqN で small、v > sqN で large |
素数でない p でも更新する | 不正な除去が起きる | get_cnt(p) == get_cnt(p-1) のとき skip |
p2 = p*p チェックを忘れる | v < p^2 の更新は不要 | if v < p2: continue |
次のステップ
発展問題: $\sum_{n \le N} \phi(n)$（オイラーの $\varphi$ 関数の総和）を Lucy's sieve 拡張版（Min-25 篩）で $O(N^{2/3}/\log N)$ で求める