Let \(S\) be the set of good integers not exceeding \(N\).
Let \(T\) denote the set of the integers \(X\) not exceeding \(N\) that can be represented as \(X=2\times b^2\) for some positive integer \(b\), and \(U\) denote the set of the integers \(X\) not exceeding \(N\) that can be represented as \(Y=2^2\times b^2\) for some positive integer \(b\).
We will now show that \(T\cup U=S\) and \(T\cap U=\phi\) (where \(\phi\) means the empty set).

For the former, clearly \(T\subset S\) and \(U\subset S\), so \((T\cup U)\subset S\). Meanwhile, any \(X \in S\) can be written as \(X=2^a\times b^2\), but if \(a\) is odd, i.e. if we can express \(a=2a'+1\) using a non-negative integer \(a'\), then \(X=2^{2a'+1}\times b^2=2\times (2^{a'}\times b)^2\), so \(X\in T\); if \(a\) is even, i.e. if we can express \(a=2a'+2\) using a non-negative integer \(a'\), then \(X=2^{2a'+2}\times b^2=2^2\times (2^{a'}\times b)^2\), so \(X\in U\). Therefore, \(S\subset (T\cup U)\); together with \((T\cup U)\subset S\) as mentioned earlier, we obtain \(T\cup U=S\).

For the latter, every integer in \(T\) has an odd number of prime factors \(2\), and every integer in \(U\) has an even number of prime factors \(2\), so no integer belongs to both of them, and \(T\cap U=\phi\).
Here, a positive integer \(X\) is said to have \(k\) prime factors \(2\) when \(X=2^k\times B\) for some odd number \(B\); for each integer, we can uniquely determine the number of prime factors \(2\) that the integer has. (In other words, this value is the number of times that \(X\) can repeatedly divide \(2\).)

Hence, \(T\cup U=S\) and \(T\cap U=\phi\), which implies \(\lvert S\rvert=\lvert T\rvert + \lvert U\rvert\). Here, \(\lvert S\rvert, \lvert T\rvert, \lvert U\rvert\) denotes the number of elements in \(S,T,U\), respectively.

The integers that can be written as \(X=2\times b^2\) for some positive integer \(b\) are \(2=(2\times 1^2)\), \(8=(2\times 2^2)\), \(18=(2\times 3^2)\), \(\ldots\), and so on, so \(\lvert T\rvert \) equals the maximum non-negative integer \(b\) such that \(2\times b^2\leq N\). Likewise, \(\lvert U\rvert \) equals the maximum non-negative integer \(b\) such that \(2^2\times c^2\leq N\).

One can find the maximum non-negative integer \(b\) with, for instance, binary search, because \(2\times b^2\) is strictly monotonically increasing with respect to non-negative integers \(b\). Since \(b\) is at most \(\sqrt{N}\), it can be found in \(O(\log N)\) time. One can also find the maximum non-negative integer \(c\) with \(2^2\times c^2\leq N\).

Now that we have found the values \(\lvert T\rvert\) and \(\lvert U\rvert\), the answer can be decided as the sum of them. The time complexity is \(O(\log N)\), which is fast enough.
Thus, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;


int main(void){
	long long n;
	long long l,r,m,ans=0;
	const long long inf = (long long)1e9;
	cin >> n;

	l=0;r=inf;
	while((l+1)<r){
		m=(l+r)/2;
		if((m*m*2)<=n)l=m;
		else r=m;
	}
	ans+=l;

	l=0;r=inf;
	while((l+1)<r){
		m=(l+r)/2;
		if((m*m*4)<=n)l=m;
		else r=m;
	}
	ans+=l;

	cout << ans << endl;
	return 0;
}