ABC300D - AABCC

考え方

素数はエラトステネスの篩（ふるい）で列挙できる．

$a^{5} < a^{2}b c^{2} \leq 10^{12}$より$a < 252$．
$2^{2}\times 3 \times c^{2} \leq 10^{12}$より$c \leq 10^{6}/\sqrt{12} < 288,676$．

この範囲で全て調べれば良い．

回答例

N = int(input())

MAX = 300000
prime = []
is_prime = [True] * (MAX + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, MAX + 1):
    if is_prime[i]:
        prime.append(i)
        for j in range(2*i, MAX + 1, i):
            is_prime[j] = False

ans = 0
num = len(prime)
for i in range(num):
    a = prime[i]
    if a > 252: continue
    for j in range(i + 1, num):
        b = prime[j]
        for k in range(j + 1, num):
            c = prime[k]
            if (a ** 2) * b * (c ** 2) <= N:
                ans += 1
            else:
                break
print(ans)