A number k is called a square number if for some value of d > 1, k % (d*d) = 0. Given a number N, find the total number of positive square numbers less than or equal to N.

See the logic of recursive inclusion and exclusion

/*
   // Difficulty : Hard  Prerequisite:  Inclusion-Exclusion Principles, Sieve of Eratosthenes  Time complexity: O(sqrt(n)*log(n))   If any integer has a perfect square as factor, then it is guaranteed that it has a square of prime as a factor too. So we need to count the integers less than or equal to N which have square of primes as a factor.  Let us look at the number of integers less than N which has 2*2=4 as factor. Every 4th number has 4 as factor(4,8,12,16..) so there are total [N/4] numbers who has 4 as factor, similarly there are [N/9] numbers who has 9 as factor. (Here [N] is greatest integer of N).  Now to calculate the number of integer who has both 4,9 as factor, we cant simply add [N/4] and [N/9] as we are counting numbers with 36 as factor two times. To avoid this we use Inclusion-Exclusion Principle. To avoid the double counting of number with 36 as factor ,we subtract [N/36] from our answer.  So number of integers with both 4,9 as factor=[N/4]+[N/9]-[N/36]  Similarly, the number of integers with 4,9,25 as factors=[N/4]+[N/9]+[N/25]-[N/36]-[N/100]-[N/225]+[N/900]  The general formula can be seen here : Inclusion-Exclusion Formula  Now to find the number of integers less than N which has a perfect square as factor, we recursively add and subtract the answers as discussed above till the value of greatest integer reaches zero.
*/
class Solution {
  public:
  bool a[100000];
    long long primes[100000],in=0;
    
    void Sieve(int n)
    {
        memset(a,true,sizeof(a));
        a[1]=false;
        for(int i=2; i*i<=n; i++)
        {
            if(a[i])
            {
                for(int j=2*i; j<=n; j+=i)
                    a[j]=false;
            }
        }
        for(int i=2; i<=n; i++)
        {
            if(a[i])
                primes[in++]=i;
        }
    }
    
    long long calc(long long in, long long cur, long long k)
    {
		long long newCur = primes[in]*primes[in]*cur;
		long long res=0;
		if(newCur>k)//case when [k/newCur]=0, so we dont need to recurse any further
            return 0;
        //include this to answer
		res += k/(newCur);
		res += calc(in+1,cur,k);
		
		//exclude from answer the repeated ones
		res -= calc(in+1,newCur,k);
		return res;
    }
    
    long long sqNum(long long N) {
        
        Sieve(100000);
        
        long long ans = calc(0,1,N);
        
        return ans;
    }
};
//https://practice.geeksforgeeks.org/problems/square-numbers1954/1/?page=1&status[]=unsolved&curated[]=7&sortBy=submissions#