# トグルとはなんなのか... # 我々はその正体を追い求めるべく、 # さらに密林の奥へ探索するのだった... # 全ての人が立つ # |はい!|はい!|はい!|はい!| # | 1 | 1 | 1 | 1 | # 次! 2ばんの人から1人おきにトグれ! # | 1 | 0(シッダウン) | 1 | 0(シッダウン)| # 実験 # 123456789 # 111111111 # -t-t-t-t- # --t--t--t # ---t---t- # ----t---- # -----t--- # ------t-- # -------t- # --------t # シミュレーションすると宇宙大爆発 # トグル回数の偶奇を見ればいい # n番目(1-indexed)について # nがトグル回数は、 # n = 10: 10 = 2*5 -> 1,2,5,10: 3こ = 約数の個数 # n = 12: 12 = 2^2*3 -> 1,2,3,4,6,12: = 約数の個数 # 1は初回でトグルから、(トグル回数) = (約数の個数) N = int(input()) # 約数の個数の偶奇を求めたい # もし奇数なら立っている # もし偶数なら座っている # 辞書 from collections import defaultdict yakusuu_cnt = defaultdict(int) yakusuu_cnt[1] = 1 for n in range(2,N+1): p = 1 while p*p <= n: if n%p == 0: yakusuu_cnt[n] += 1 if n//p != p: yakusuu_cnt[n] += 1 p += 1 # debug-print # print(yakusuu_cnt) ans = 0 for i in range(1,N+1): if yakusuu_cnt[i]%2: ans += 1 print(ans)