Submission #42888284

---

Source Code Expand

def D():
    from bisect import bisect_left
    
    N = int(input())
    f_max = int((N / 12) ** (1/2)) + 1
    
    seed = [1] * (f_max + 1)
    
    for i in range(3, f_max + 1, 2):
        if not seed[i]: continue
        for j in range(i * 2, f_max + 1, i):
            seed[j] = 0
            
    facs = [2]
    for i in range(3, f_max + 1, 2):
        if seed[i]: facs.append(i)
    
    ans = 0
    for i in range(len(facs) - 2):
        if facs[i] ** 2 * facs[i + 1] * facs[i + 2] ** 2 > N:
            break
        for j in range(i + 1, len(facs) - 1):
            a2b = facs[i] ** 2 * facs[j]
            idx = bisect_left(facs, (N / a2b) ** (1/2))
            if idx <= j:
                break
            elif idx >= len(facs):
                ans += len(facs) - 1 - j
            elif a2b * facs[idx] ** 2 == N:
                ans += idx - j
            else:
                ans += idx - j - 1
                
    print(ans)    
    
    
D()

Submission Info

Judge Result