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)