AtCoder Beginner Contest 254 D

https://atcoder.jp/contests/abc254/tasks/abc254_d

1からNまでの平方項をなくした数を求めます。例えば、12なら4で割って3です。これはエラトステネスのふるい的にで求められます。
12にかけて平方数になる数は、3, 12, 27, ...です。ということは、N/12以下の3×平方数だから、です。はニュートン法でで求められると思いますが、現実にはなので、全体ではの計算量でしょう。

# coding: utf-8
# Together Square

from itertools import *


#################### library ####################

def read_int():
    return int(raw_input())


#################### process ####################

def read_input():
    N = read_int()
    return N

def make_prime_table(N):
    if N == 1:
        return []
    
    a = [ True ] * (N + 1)
    for p in takewhile(lambda p: p * p <= N, (n for n in count(2) if a[n])):
        for m in xrange(p * p, N + 1, p):
            a[m] = False
    return [ n for n in xrange(2, N + 1) if a[n] ]

def div_pow(n, d):
    e = 0
    while n % d == 0:
        e += 1
        n /= d
    return e, n

from math import sqrt
def not_square_table(N):
    primes = make_prime_table(int(sqrt(N)))
    a = range(N+1)
    for p in primes:
        for n in range(p*p, N+1, p*p):
            e, a[n] = div_pow(a[n], p*p)
    return a

def F(N):
    a = not_square_table(N)
    s = 0
    for i in range(1, N+1):
        s += int(sqrt(N / a[i]))
    return s


#################### main ####################

N = read_input()
print F(N)