from itertools import count from tools import int_sqrt
N = 10 ** 18 M = int(N ** (1 / 4)) square_free = [1] * (M + 1) for i inrange(2, int_sqrt(M) + 1): k = i * i for j inrange(k, M + 1, k): square_free[j] = 0 ans = 0 for z in count(1, 1): z5 = z ** 5 if z ** 5 > N: break if square_free[z]: for y in count(1, 1): y4 = y ** 4 mul = y4 * z5 if mul > N: break if square_free[y] and square_free[z * y]: for x in count(1, 1): x3 = x ** 3 if mul * x3 > N: break ans += N // (mul * x3) print(ans)