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.
 
Example 1:
Input:
N = 3
Output:
0
Explanation:
There are no square numbers which
are less than or equal to 3.
Example 2:
Input:
N = 4
Output:
1
Explanation:
4 is the only square number less than
or equal to 4.
4 is divisible by (2*2).
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function sqNum() which takes an Integer N as input and returns the number of square numbers less tha or equal to N.
 
Expected Time Complexity: O(sqrt(N)*log(N) )
Expected Auxiliary Space: O(sqrt(N))
 
Constraints:
1 <= N <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def sqNum(self, N):
        # code here 

Solutions:
import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def __init__(self):
		self.a = [True] * 100010
		self.primes = [0] * 100010
		self.in_ = 0

	def Sieve(self, n):
		self.a[1] = False
		for i in range(2, int(n ** 0.5) + 1):
			if self.a[i]:
				for j in range(2 * i, n + 1, i):
					self.a[j] = False
		for i in range(2, n + 1):
			if self.a[i]:
				self.primes[self.in_] = i
				self.in_ += 1

	def calc(self, in_, cur, k):
		newCur = self.primes[in_] * self.primes[in_] * cur
		res = 0
		if newCur > k:
			return 0
		res += k // newCur
		res += self.calc(in_ + 1, cur, k)
		res -= self.calc(in_ + 1, newCur, k)
		return res

	def sqNum(self, N):
		self.Sieve(100000)
		ans = self.calc(0, 1, N)
		return ans