考え方 回答例 考え方素数はエラトステネスの篩（ふるい）で列挙できる．$a^{5} $2^{2}\times 3 \times c^{2} \leq 10^{12}$より$c \leq 10^{6}/\sqrt{12} この範囲で全て調べれば良い．回答例 N = int(input()) MAX = 300000 prime = [] is_prime = [True] …

考え方 回答例 考え方$N \leq 10^{18}$なので$q \leq 10^{6}$．よって，$10^{6}$以下の素数を列挙して，$\min(N /\!/ q^{3}, q - 1)$以下の素数の数を数え上げれば良い． エラトステネスの篩（Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめまし…

考え方 回答例 考え方エラトステネスの篩-likeな考え方で解ける． AtCoder - 解法パターンの整理 - 競プロはじめました以下のループは$O(N \log N)$であることがポイント． for i in range(N): for j in range(i, N + 1, i): # 処理 回答例 from collections…