正の整数 \((a,b)\) を用いて \(2^a\times b^2\) と表せる整数は、\(a\) が偶数なら平方数を \(4\) 倍した数、 \(a\) が奇数なら平方数を \(2\) 倍した数になります。

よって、 \(N\) 以下の良い整数の個数は \(\left\lfloor\sqrt{\frac{N}2} \right\rfloor+\left\lfloor\sqrt{\frac{N}4} \right\rfloor\) 個になります。

実装の際に sqrt 関数をそのまま使うと小数点誤差により正しい値が得られない場合があるので注意してください。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
	long long n;
	cin >> n;
	cout << (long long)sqrtl(n / 2) + (long long)sqrtl(n / 4) << endl;
}

実装例(Python)

from math import isqrt

n = int(input())
print(isqrt(n // 2) + isqrt(n // 4))