ABC250D - 250-like Number

考え方

$N \leq 10^{18}$なので$q \leq 10^{6}$．よって，$10^{6}$以下の素数を列挙して，$\min(N /\!/ q^{3}, q - 1)$以下の素数の数を数え上げれば良い．

エラトステネスの篩（Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめました）を使えば，$O(N\log\log N)$で素数を列挙できる．

回答例

N = int(input())

cumsum = [0] * (10 ** 6 + 1)
is_prime = [True] * (10 ** 6 + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, 10 ** 6 + 1):
    if is_prime[i]:
        cumsum[i] = cumsum[i - 1] + 1
        for j in range(2 * i, 10 ** 6 + 1, i):
            is_prime[j] = False
    else:
        cumsum[i] = cumsum[i - 1]

ans = 0
for i in range(1, 10 ** 6 + 1):
    if is_prime[i]:
        ans += cumsum[min(N // (i ** 3), i - 1)]

print(ans)

【参考】Submission #31524869 - AtCoder Beginner Contest 250 (【解説 実況】ABC250 AからD【かつっぱ】 - YouTube)