Submission #32292042

---

Source Code Expand

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
n = int(input())
squares = []
i = 1
while i**2 <= n:
    squares.append(i**2)
    i += 1
ans = 0
for i in range(1, n+1):
    x = i
    fact = factorization(i)
    odd = 1
    for a, cnt in fact:
        if cnt % 2 == 1: odd *= a
    for j in squares:
        if odd * j > n: continue
        ans += 1
print(ans)

Submission Info

Judge Result