You are given a list of q queries and for every query, you are given an integer N.  The task is to find how many numbers(less than or equal to N) have number of divisors exactly equal to 3.
Example 1:
Input:
q = 1
query[0] = 6
Output:
1
Explanation:
There is only one number 4 which has
exactly three divisors 1, 2 and 4 and
less than equal to 6.
Example 2:
Input:
q = 2
query[0] = 6
query[1] = 10
Output:
1
2
Explanation:
For query 1 it is covered in the
example 1.
query 2: There are two numbers 4 and 9
having exactly 3 divisors and less than
equal to 10.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function threeDivisors() which takes an integer q and a list of integer of size q as input parameter and returns the list containing the count of the numbers having exactly 3 divisors for each query.
Expected Time Complexity: O(q*N*log(log(N)))
Expected Auxiliary Space: O(N), where N is min(10^6,N)
Constraints : 
1 <= q <= 10^3
1 <= query[i] <= 10^12

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3





class Solution:

	def threeDivisors(self, query, q):

		# code here

Solutions:
import math
import bisect

class Solution:

	def threeDivisors(self, query, q):
		maxn = max(query)
		ans = []
		d = {}
		primes = [1] * int(math.sqrt(maxn) + 2)
		for i in range(2, len(primes)):
			if primes[i] == 1:
				j = 2
				while j * i < len(primes):
					primes[j * i] = 0
					j += 1
		for _ in range(2, maxn + 1):
			sq = math.sqrt(_)
			if sq == int(sq) and primes[int(sq)] == 1:
				d[_] = int(sq)
		res = sorted(d.keys())
		ans = []
		for _ in query:
			ans.append(bisect.bisect_left(res, _ + 1))
		return ans


from math import sqrt

class Solution:

	def threeDivisors(self, query, q):
		primes = []
		mx = 1000001
		sieve = [True] * mx
		for i in range(2, mx):
			if sieve[i]:
				primes.append(i)
				for j in range(i * i, mx, i):
					sieve[j] = False
		l = []
		for i in query:
			c = 0
			j = 0
			while primes[j] * primes[j] <= i:
				j += 1
				c += 1
			l.append(c)
		return l


class Solution:

	def threeDivisors(self, query, q):
		ans = []
		m = max(query)
		a = Solution.prime(m)
		if q == 1:
			return [len(a)]
		c = 0
		for i in query:
			c = 0
			for j in a:
				if j > i:
					break
				c += 1
			ans.append(c)
		return ans

	def prime(N):
		d = []
		b = [1 for i in range(N + 1)]
		for i in range(2, N + 1):
			j = 2 * i
			while j <= N:
				b[j] += 1
				j += i
		c = []
		for i in range(4, N + 1):
			if b[i] == 2:
				c.append(i)
		return c


import math

class Solution:

	def __init__(self):
		self.psl = self.primesq()

	def primesq(self):
		n = int(1000000.0)
		lim = int(math.sqrt(n)) + 1
		pl = [True] * (n + 1)
		for i in range(2, lim):
			if pl[i]:
				for j in range(i * i, n + 1, i):
					pl[j] = False
		res = [x * x for x in range(2, n + 1) if pl[x]]
		return res

	def bsf(self, arr, k):
		(l, h, idx) = (0, len(arr) - 1, -1)
		while l <= h:
			m = (l + h) // 2
			if arr[m] > k:
				h = m - 1
			else:
				idx = m
				l = m + 1
		return idx + 1

	def threeDivisors(self, query, q):
		res = []
		for i in range(q):
			t = self.bsf(self.psl, query[i])
			res.append(t)
		return res


from math import sqrt

class Solution:

	def isPrime(self, n):
		prime_flag = 0
		if n > 1:
			for i in range(2, int(sqrt(n)) + 1):
				if n % i == 0:
					prime_flag = 1
					break
			if prime_flag == 0:
				return True
			else:
				return False
		else:
			return False

	def threeDivisors(self, query, q):
		answer = []
		for x in query:
			num = int(sqrt(x))
			cnt = 0
			for i in range(2, num + 1):
				check = ob.isPrime(i)
				cnt = cnt + check
			answer.append(cnt)
		return answer


from math import sqrt

class Solution:

	def threeDivisors(self, query, q):
		m = int(sqrt(max(query)))
		prime = [True] * (m + 1)
		(prime[0], prime[1]) = (False, False)
		for i in range(2, len(prime)):
			if not prime[i]:
				continue
			for j in range(i * i, len(prime), i):
				prime[j] = False
		prime = [i for (i, e) in enumerate(prime) if e]
		ans = [0] * q
		for i in range(q):
			for k in prime:
				if k * k > query[i]:
					break
				ans[i] += 1
		return ans


class Solution:

	def threeDivisors(self, query, q):
		t = []
		for i in query:
			t.append(len(self.slst(int(i ** 0.5))))
		return t

	def slst(self, n):
		lst = list(range(2, n + 1))
		p = 2
		while p * p <= n:
			for i in range(p - 2, n - n % p, p):
				if lst[i] % p == 0 and lst[i] != p:
					lst[i] = 0
			p = self.getNxtPn(p + 1, n)
		return list(filter(lambda x: x > 0, lst))

	def getNxtPn(self, p, n):
		for i in range(p, n):
			for j in range(2, round(i ** 0.5) + 1):
				if i % j == 0:
					break
				if j == round(i ** 0.5):
					return i
		return -1


class Solution:

	def threeDivisors(self, query, q):

		def primes(n):
			l = []
			for i in range(0, n + 1):
				l.append(i)
			for j in l:
				if j == 0 or j == 1:
					continue
				m = 2
				while j * m <= n:
					l[j * m] = 0
					m = m + 1
			prime_list = []
			for k in l:
				if k == 0 or k == 1:
					continue
				prime_list.append(k)
			return prime_list
		c_list = []
		for n in query:
			prime_list = primes(n)
			c = 0
			for k in prime_list:
				if k * k <= n:
					c = c + 1
				else:
					break
			c_list.append(c)
		return c_list


import math

class Solution:

	def countd(self, num):
		n = int(math.sqrt(num))
		c = 1
		for i in range(3, n + 1):
			for j in range(2, int(math.sqrt(i)) + 1):
				if i % j == 0:
					break
			else:
				c += 1
		return c

	def threeDivisors(self, query, q):
		ar = []
		for i in range(q):
			if query[i] < 4:
				ar.append(0)
			else:
				ar.append(self.countd(query[i]))
		return ar


class Solution:

	def threeDivisors(self, query, q):

		def prime_num(x):
			for k in range(2, x):
				if x % k == 0:
					return False
			return True
		lst = []
		p = 0
		for i in query:
			if p:
				lst.append(p)
				p = 0
			if i < 4:
				lst.append(0)
			for j in range(1, int(i ** 0.5) + 1):
				if prime_num(j):
					if j ** 2 <= i and j != 1:
						p += 1
		if p > 0:
			lst.append(p)
		return lst


class Solution:

	def __init__(self):
		self.dp = dict()

	def c3(self, n):
		for x in range(2, int(n ** 0.5)):
			if n % x == 0:
				return 0
		return 1

	def tra(self, m):
		count = 0
		for x in range(1, m + 1):
			if x != 1 and int(x ** 0.5) ** 2 == x:
				count += self.c3(x)
			self.dp[x] = count

	def threeDivisors(self, query, q):
		ans = []
		m = max(query)
		self.tra(m)
		return [self.dp[x] for x in query]


prime = [1] * 1000001
prime1 = [1] * 1000001
primeArray = []

def sieveOfEratosthenes(N):
	i = 2
	while i * i <= N:
		if prime1[i]:
			for j in range(i * i, N + 1, i):
				prime1[j] = 0
		i += 1
	for i in range(2, N + 1):
		if prime1[i]:
			primeArray.append(i)

class Solution:

	def solve(self, n):
		counter = 0
		index = 0
		currNum = primeArray[index] * primeArray[index]
		while currNum <= n:
			counter += 1
			index += 1
			if index == len(primeArray):
				break
			currNum = primeArray[index] * primeArray[index]
		return counter

	def threeDivisors(self, query, q):
		sieveOfEratosthenes(1000000)
		ans = []
		for el in query:
			ans.append(self.solve(el))
		return ans


class Solution:

	def threeDivisors(self, query, q):
		count = 0

		def Prime_check2(n: int) -> bool:
			if n == 1 or n == 0:
				return False
			if n == 2 or n == 3:
				return True
			if n % 2 == 0 or n % 3 == 0:
				return False
			i = 5
			while i * i <= n:
				if n % i == 0 or n % (i + 2) == 0:
					return False
				i += 6
			return True
		listOfCount = []
		for n in query:
			count = 0
			for i in range(1, 1 + int(n ** (1 / 2))):
				if Prime_check2(i):
					count += 1
			listOfCount.append(count)
		return listOfCount


import math

def isPrime(N):
	if N <= 1:
		return 0
	if N == 2 or N == 3:
		return 1
	if N % 2 == 0 or N % 3 == 0:
		return 0
	for i in range(5, int(math.sqrt(N)) + 1, 6):
		if N % i == 0 or N % (i + 2) == 0:
			return 0
	return 1

class Solution:

	def threeDivisors(self, query, q):
		L = []
		for i in query:
			count = 0
			for j in range(2, int(math.sqrt(i)) + 1):
				if isPrime(j):
					count += 1
			L.append(count)
		return L


class Solution:

	def threeDivisors(self, query, q):
		counter = []
		for j in range(q):
			prime = [True] * (query[j] + 1)
			prime[0] = prime[1] = False
			cnt = 0
			p = 2
			while p * p <= query[j]:
				if prime[p] == True:
					for k in range(p * 2, query[j] + 1, p):
						prime[k] = False
				p += 1
			i = 0
			while i * i <= query[j]:
				if prime[i]:
					cnt += 1
				i += 1
			counter.append(cnt)
		return counter


import math

class Solution:

	def isPrime(self, n):
		if n == 2 or n == 3:
			return True
		i = 2
		while i * i <= n:
			if n % i == 0:
				return False
			i += 1
		return True

	def threeDivisors(self, query, q):
		result = []
		for num in query:
			count = 0
			i = 2
			while i * i <= num:
				if i * i <= num and self.isPrime(i):
					count += 1
				i += 1
			result.append(count)
		return result


import math
import bisect

class Solution:

	def isPrime(self, n):
		if n == 1:
			return False
		for i in range(2, int(math.sqrt(N)) + 1):
			if N % i == 0:
				return False
		return True

	def threeDivisors(self, query, q):
		ans = []
		maxi = max(query)
		a = [True for _ in range(maxi + 1)]
		primes = []
		for i in range(2, maxi + 1):
			if a[i]:
				for j in range(i * i, maxi + 1, i):
					a[j] = False
		for i in range(2, maxi + 1):
			if a[i]:
				primes.append(i)
		for x in query:
			c = 0
			for y in primes:
				if y * y <= x:
					c += 1
			ans.append(c)
		return ans


class Solution:

	def threeDivisors(self, query, q):
		length = min(10 ** 6 + 1, int(max(query) ** 0.5) + 1)
		primes = [0] * length
		seive = [False] * length
		for i in range(2, length):
			primes[i] = primes[i - 1]
			if not seive[i]:
				primes[i] += 1
				for j in range(i, length, i):
					seive[j] = True
		ans = []
		for q in query:
			ans.append(primes[int(q ** 0.5)])
		return ans


class Solution:

	def threeDivisors(self, query, q):
		m = max(query)
		prime = [True for i in range(m + 1)]
		self.FindPrimes(prime, m)
		out = []
		for j in query:
			count = 0
			i = 2
			while i * i <= j:
				if prime[i]:
					count = count + 1
				i += 1
			out.append(count)
		return out

	def FindPrimes(self, prime, m):
		p = 2
		while p * p <= m:
			if prime[p] == True:
				for i in range(p * p, m + 1, p):
					prime[i] = False
			p += 1


class Solution:

	def threeDivisors(self, query, q):
		N = max(query)
		ans = []
		prime = [1] * (N + 5)
		prime[0] = prime[1] = 0
		for i in range(N + 5):
			if prime[i]:
				for j in range(2 * i, N + 5, i):
					prime[j] = 0
		for i in range(1, N + 5):
			prime[i] += prime[i - 1]
		for i in range(q):
			qu = int(query[i] ** 0.5)
			ans += [prime[qu]]
		return ans


from math import floor, sqrt
from bisect import bisect

class Solution:

	def sieve(self, n):
		primes = [1] * (n + 1)
		p = 2
		while p * p <= n:
			for i in range(p * p, n + 1, p):
				primes[i] = 0
			p += 1
		return primes

	def threeDivisors(self, query, q):
		num = int(sqrt(max(query)))
		primes = self.sieve(num)
		primes = [i for i in range(len(primes)) if primes[i]][2:]
		return [bisect(primes, sqrt(num)) for num in query]


class Solution:

	def threeDivisors(self, query, q):
		querySort = sorted(query)
		counterMax = 0
		counter = 2
		dict_ = {}
		res = []
		for i in querySort:
			for j in range(counter, i + 1):
				if j ** 2 > i:
					counter = j
					break
				if self.isPrime(j):
					counterMax += 1
			if i not in dict_:
				dict_[i] = counterMax
		for i in query:
			res.append(dict_[i])
		return res

	def isPrime(self, num):
		if num <= 1:
			return 0
		elif num <= 3:
			return 1
		for i in range(2, int(num ** 0.5) + 1):
			if num % i == 0:
				return 0
		return 1


class Solution:

	def threeDivisors(self, query, q):
		prime_list = []
		for test_num in query:
			div_list = []
			prime_count = -1
			if test_num == 0 or test_num == 1 or test_num == 2 or (test_num == 3):
				prime_count = 0
				prime_list.append(prime_count)
				continue
			for count in range(2, test_num):
				is_prime = True
				final_count = int(count / 2) + 1
				for num in range(2, final_count):
					if count % num == 0:
						is_prime = False
				if is_prime:
					prime_sq = count * count
					prime_count = prime_count + 1
				if prime_sq > test_num:
					break
			prime_list.append(prime_count)
		return prime_list


class Solution:

	def isPrime(self, num):
		for i in range(2, num):
			if num % i == 0:
				return False
		else:
			return True

	def threeDivisors(self, query, q):
		l = []
		ans = []
		for n in query:
			l.append(int(n ** 0.5))
		for i in l:
			count = 0
			for j in range(2, i + 1):
				if self.isPrime(j):
					count += 1
			ans.append(count)
		return ans


import math

class Solution:

	def threeDivisors(self, query, q):

		def prime(n):
			f = 0
			for k in range(2, int(math.sqrt(n)) + 1):
				if n % k == 0:
					f = 1
			if f == 0:
				return True
			else:
				return False
		d = []
		for i in range(q):
			c = 0
			for j in range(2, int(math.sqrt(query[i])) + 1):
				if prime(j):
					c += 1
			d.append(c)
		return d


import math
N = 10 ** 6
p = [True for i in range(N)]
for i in range(2, N):
	if p[i]:
		for j in range(2 * i, N, i):
			p[j] = False
p[0] = p[1] = 0
p[2] = 1
for i in range(3, N):
	p[i] = p[i - 1] + 1 if p[i] and i * i & 1 == 1 else p[i - 1]

class Solution:

	def threeDivisors(self, query, N):
		res = []
		for q in query:
			res.append(p[int(q ** 0.5)])
		return res


import math

class Solution:
	MAX = 1000
	prefix = [0] * (MAX + 1)

	def buildprefix(self):
		prime = [1] * (Solution.MAX + 1)
		p = 2
		while p * p <= Solution.MAX:
			if prime[p] == 1:
				i = p * 2
				while i <= Solution.MAX:
					prime[i] = 0
					i += p
			p += 1
		for p in range(2, Solution.MAX + 1):
			Solution.prefix[p] = Solution.prefix[p - 1]
			if prime[p] == 1:
				Solution.prefix[p] += 1

	def qp(self, L, R):
		return Solution.prefix[R] - Solution.prefix[L - 1]

	def nearestpow(self, n):
		return int(math.sqrt(n))

	def threeDivisors(self, query, q):
		for p in range(q):
			n = query[p]
			if n == 1 or n == 2 or n == 3:
				query[p] = 0
				continue
			k = self.nearestpow(n)
			self.buildprefix()
			val = self.qp(2, k)
			query[p] = val
			Solution.Max = 1000000
			Solution.prefix = [0] * (Solution.MAX + 1)
		return query


class Solution:

	def threeDivisors(self, query, q):
		n = max(query)
		prime = [1] * (n + 1)
		p = 2
		div = [0] * (n + 1)
		res = [0] * (n + 1)
		ans = []
		(prime[0], prime[1]) = (0, 0)
		while p * p <= n:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
			p += 1
		for i in range(int(n ** 0.5) + 1):
			if prime[i] == 1:
				div[i * i] = 1
		for i in range(1, n + 1):
			res[i] = div[i] + res[i - 1]
		for i in query:
			ans.append(res[i])
		return ans


class Solution:

	def isPrime(self, i):
		r = int(pow(i, 0.5))
		for k in range(2, r + 1):
			if i % k == 0:
				return False
		return True

	def threeDivisors(self, query, q):
		maxi = max(query)
		ans = []
		i = 2
		while i * i <= maxi:
			if self.isPrime(i):
				ans.append(i * i)
			i += 1
		result = []
		for i in query:
			start = 0
			end = len(ans) - 1
			while start <= end:
				mid = (start + end) // 2
				if ans[mid] > i:
					end = mid - 1
				else:
					start = mid + 1
			if start - 1 >= 0:
				result.append(start)
				continue
			result.append(0)
		return result


def isprime(num):
	for i in range(2, int(num ** 0.5) + 1):
		if num % i == 0:
			return False
	return True

def isthree(num):
	count = 0
	if num >= 4:
		count += 1
	i = 3
	while i * i <= num:
		if isprime(i):
			count += 1
		i += 2
	return count

class Solution:

	def threeDivisors(self, query, q):
		ans = []
		for i in range(q):
			ans.append(isthree(query[i]))
		return ans


class Solution:

	def np(n):
		c = 0
		for i in range(2, n + 1):
			p = 0
			for j in range(2, i):
				if i % j == 0:
					p = 1
			if p == 0:
				c += 1
		return c

	def threeDivisors(self, query, q):
		a = []
		for i in query:
			b = Solution.np(int(i ** 0.5))
			a.append(b)
		return a


import math

class Solution:

	def threeDivisors(self, query, q):
		n = math.floor(math.sqrt(max(query)))
		prime = [True] * (n + 1)
		prime[0] = prime[1] = False
		for i in range(2, n + 1):
			if prime[i]:
				for j in range(i * i, n + 1, i):
					prime[j] = False
		dp = [0] * (n + 1)
		for i in range(2, n + 1):
			dp[i] = dp[i - 1]
			if prime[i]:
				dp[i] += 1
		ans = []
		for i in query:
			val = math.floor(math.sqrt(i))
			ans.append(dp[val])
		return ans


class Solution:

	def threeDivisors(self, query, q):

		def nd(n):
			i = 2
			c = 0
			while i * i <= n:
				if isPrime(i):
					if i * i <= n:
						c = c + 1
				i += 1
			return c

		def isPrime(n):
			i = 2
			while i * i <= n:
				if n % i == 0:
					return False
				i += 1
			return True
		for i in range(q):
			query[i] = nd(query[i])
		return query


import bisect

class Solution:

	def threeDivisors(self, query, q):
		primes = [True for i in range(10 ** 6 + 1)]
		primes[0] = False
		primes[1] = False
		p = 2
		while p * p <= 10 ** 6 + 1:
			if primes[p] == True:
				for i in range(p * p, 10 ** 6 + 1, p):
					primes[i] = False
			p += 1
		squares = []
		for i in range(2, 10 ** 6 + 1):
			if primes[i] == True:
				squares.append(i * i)
		res = []
		for q in query:
			res.append(bisect.bisect(squares, q))
		return res


class Solution:

	def threeDivisors(self, query, q):

		def solve(n):
			dp = [1] * (n + 1)
			i = 2
			while i * i <= n:
				if dp[i]:
					for j in range(i * i, n + 1, i):
						dp[j] = 0
				i += 1
			return dp
		from bisect import bisect_right
		val = int(max(query) ** 0.5)
		dp = solve(val)
		dp = [i for i in range(len(dp)) if dp[i]][2:]
		return [bisect_right(dp, int(i ** 0.5)) for i in query]


class Solution:

	def threeDivisors(self, query, q):

		def isPrime(num):
			for c in range(2, num):
				if num % c == 0:
					return False
			return True
		a = []
		for i in range(q):
			n = query[i]
			j = 2
			count = 0
			while j < n:
				if j * j in range(2, n + 1) and isPrime(j):
					count = count + 1
				j = j + 1
			a.append(count)
		return a


class Solution:

	def threeDivisors(self, query, q):

		def fun(s):
			if s <= 1:
				return False
			for k in range(2, int(s ** 0.5) + 1):
				if s % k == 0:
					return False
			else:
				return True
		res = []
		for i in query:
			t = 0
			for j in range(2, int(i ** 0.5) + 1):
				if fun(j):
					t += 1
			res.append(t)
		return res


class Solution:

	def threeDivisors(self, query, q):
		max_query = max(query)
		prime = [True for i in range(max_query + 1)]
		p = 2
		prime[0] = prime[1] = False
		while p * p <= max_query:
			if prime[p]:
				for val in range(p * 2, max_query + 1, p):
					prime[val] = False
			p += 1
		ans = []
		i = 0
		divisor = [False for i in range(max_query + 1)]
		while i * i <= max_query:
			if prime[i]:
				divisor[i * i] = True
			i += 1
		for val in query:
			ans.append(sum(divisor[:val + 1]))
		return ans


import math

class Solution:

	def threeDivisors(self, query, q):
		mx = int(math.sqrt(max(query)))
		prime = [True] * (mx + 1)
		for i in range(2, mx + 1):
			if prime[i]:
				j = i + i
				while j <= mx:
					prime[j] = False
					j += i
		count = [0] * (mx + 1)
		for i in range(2, mx + 1):
			count[i] += count[i - 1]
			if prime[i]:
				count[i] += 1
		ans = []
		for i in range(q):
			a = int(math.sqrt(query[i]))
			ans.append(count[a])
		return ans


class Solution:

	def threeDivisors(self, query, q):
		x = []
		for i in range(q):
			a = query[i]
			c = 0
			for j in range(2, a + 1):
				d = 1
				for k in range(2, j):
					if j % k == 0:
						d = 0
						break
				if d == 1:
					if j * j <= a:
						c += 1
					else:
						break
			x.append(c)
		return x


class Solution:

	def threeDivisors(self, query, q):

		def prime(n):
			if n == 1:
				return False
			if n % 1 != 0:
				return False
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		l = []
		for i in range(q):
			a = query[i] ** 0.5
			co = 0
			for i in range(1, int(a) + 1):
				if prime(i):
					co += 1
			l.append(co)
		return l


class Solution:

	def threeDivisors(self, query, q):

		def solve(n):
			for i in range(2, n):
				if n % i == 0:
					return False
			return True
		ans = []
		c = 0
		for i in query:
			if c:
				ans.append(c)
				c = 0
			if i < 4:
				ans.append(0)
			for j in range(1, int(i ** 0.5) + 1):
				if solve(j):
					if j ** 2 <= i and j != 1:
						c += 1
		if c > 0:
			ans.append(c)
		return ans