Given two positive integers L and R, return count of numbers having exactly 3 divisors from L to R inclusive.
 
Example 1:
Input:
L = 1, R = 10
Output:
2
Explanation:
4 and 9 are two numbers between 1 and 10
and have exactly 3 divisors.
Example 2:
Input:
L = 2, R = 5
Output:
1
Explanation:
4 is the only number between 2 and 5
and have exactly 3 divisors.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function count3DivNums() which takes 2 Integers L, and R as input and returns the count of numbers between L and R having exacly 3 divisors.
 
Expected Time Complexity: O(sqrt(R)*log(R))
Expected Auxiliary Space: O(sqrt(R))
 
Constraints:
1 <= L <= R <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code: #User function Template for python3



class Solution:

    def count3DivNums(self, L, R):

        # code here 

Solutions:
class Solution:

	def count3DivNums(self, L, R):

		def isPrime(n):
			if n == 1:
				return False
			else:
				lim = int(n ** 0.5) + 1
				for i in range(2, lim):
					if n % i == 0:
						return False
				return True
		c = 0
		if L ** 0.5 == int(L ** 0.5):
			s = int(L ** 0.5)
		else:
			s = int(L ** 0.5) + 1
		e = int(R ** 0.5) + 1
		for i in range(s, e):
			if isPrime(i):
				c += 1
		return c


class Solution:

	def count3DivNums(self, L, R):
		n = R
		sq = int(n ** 0.5)
		sieve = [True] * (sq + 1)
		sieve[0] = sieve[1] = False
		ans = 0
		for i in range(2, sq + 1):
			if sieve[i]:
				for j in range(i * i, sq + 1, i):
					sieve[j] = False
				if L <= i * i <= R:
					ans += 1
		return ans


from math import sqrt

class Solution:

	def count3DivNums(self, L, R):
		n = int(sqrt(R)) + 1
		prime = []
		sieve = [1] * n
		for i in range(2, n):
			if sieve[i]:
				for j in range(i * i, n, i):
					sieve[j] = 0
		for i in range(2, n):
			if sieve[i]:
				prime.append(i)
		c = 0
		for i in prime:
			if i * i >= L and i * i <= R:
				c += 1
		return c


from math import sqrt, ceil, floor

class Solution:

	def count3DivNums(self, L, R):
		N = ceil(sqrt(R))
		Seen = [False for _ in range(N)]
		i = 2
		while i * i <= N:
			if Seen[i]:
				i += 1
				continue
			for j in range(i * i, N, i):
				Seen[j] = True
			i += 1
		res = 0
		for i in range(2, N):
			if Seen[i]:
				continue
			if L <= i * i <= R:
				res += 1
		return res


from math import *

class Solution:

	def count3DivNums(self, L, R):
		count = 0

		def isPrime(n):
			if n == 0 or n == 1:
				return False
			if n == 2 or n == 3:
				return True
			if n % 2 == 0 or n % 3 == 0:
				return False
			for i in range(5, int(n ** 0.5) + 1, 4):
				if n % i == 0 or n % (i + 2) == 0:
					return False
			return True
		L = ceil(L ** 0.5)
		R = int(R ** 0.5) + 1
		for n in range(L, R):
			if isPrime(n):
				count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(L, R) = map(int, input().split())
		ob = Solution()
		print(ob.count3DivNums(L, R))


from math import sqrt, ceil, floor

class Solution:

	def count3DivNums(self, L, R):
		N = ceil(sqrt(R))
		Seen = [False for _ in range(N)]
		i = 2
		while i * i <= N:
			if Seen[i]:
				i += 1
				continue
			for j in range(i * i, N, i):
				Seen[j] = True
			i += 1
		res = 0
		for i in range(2, N):
			if Seen[i]:
				continue
			if L <= i * i <= R:
				res += 1
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(L, R) = map(int, input().split())
		ob = Solution()
		print(ob.count3DivNums(L, R))


def sieve(n):
	prime = []
	isprime = [True] * (n + 1)
	spf = [1] * (n + 1)
	l = 0
	for i in range(2, n + 1):
		if isprime[i]:
			prime.append(i)
			l += 1
			spf[i] = i
		j = 0
		while j < l and prime[j] <= spf[i] and (i * prime[j] < n + 1):
			spf[prime[j] * i] = prime[j]
			isprime[prime[j] * i] = False
			j += 1
	return (prime, l)

class Solution:

	def count3DivNums(self, L, R):
		r = int(R ** 0.5)
		(prime, l) = sieve(r)
		c = 0
		for i in prime:
			if i * i >= L:
				break
			c += 1
		return l - c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(L, R) = map(int, input().split())
		ob = Solution()
		print(ob.count3DivNums(L, R))


import math, bisect

class Solution:

	def count3DivNums(self, L, R):
		start = math.ceil(math.sqrt(L))
		end = math.floor(math.sqrt(R)) + 1
		ans = 0
		sieve = [1] * end
		sieve[0] = sieve[1] = 0
		for i in range(2, int(math.sqrt(end - 1)) + 1):
			j = i
			while i * j < end:
				sieve[i * j] = 0
				j += 1
		for i in range(start, end):
			if i ** 2 <= R and sieve[i]:
				ans += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(L, R) = map(int, input().split())
		ob = Solution()
		print(ob.count3DivNums(L, R))


import math

class Solution:

	def count3DivNums(self, L, R):
		c = 0
		l = math.ceil(math.sqrt(L))
		r = int(math.sqrt(R)) + 1
		for i in range(l, r):
			if self.isprime(i):
				c += 1
		return c

	def isprime(self, a):
		k = 0
		if a < 2:
			return False
		if a == 2:
			return True
		if a % 2 == 0:
			return False
		for i in range(3, int(math.sqrt(a)) + 1, 2):
			if a % i == 0:
				return False
		return True
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(L, R) = map(int, input().split())
		ob = Solution()
		print(ob.count3DivNums(L, R))


from math import sqrt

class Solution:

	def isPrime(self, x):
		if x < 2:
			return False
		if x == 2:
			return True
		if x % 2 == 0:
			return False
		for i in range(3, int(sqrt(x)) + 1, 2):
			if x % i == 0:
				return False
		return True

	def count3DivNums(self, L, R):
		DiViSoRs = 0
		L = int(sqrt(L) + 1.0)
		R = int(sqrt(R)) + 1
		for x in range(L, R):
			if self.isPrime(x):
				DiViSoRs += 1
		return DiViSoRs


import math

class Solution:

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

	def count3DivNums(self, L, R):
		count = 0
		L = int(math.sqrt(L)) + 1
		R = int(math.sqrt(R)) + 1
		for i in range(L, R):
			if self.isPrime(i):
				count += 1
		return count


class Solution:

	def count3DivNums(self, L, R):
		count = 0
		r = int(R ** 0.5)
		l = int(L ** 0.5)
		prime = [True] * (r + 1)
		dp = [0] * (r + 1)
		p = 2
		while p * p <= R:
			dp[p] += dp[p - 1]
			if prime[p] == True:
				dp[p] += 1
				for i in range(p * p, r + 1, p):
					prime[i] = False
			p += 1
		l = int(L ** 0.5)
		if l * l < L:
			l += 1
		return dp[r] - dp[l - 1]


class Solution:

	def count3DivNums(self, L, R):
		import math

		def isprime(n):
			import math
			if n == 1:
				return False
			k = int(math.sqrt(n))
			for i in range(2, k + 1):
				if n % i == 0:
					return False
			return True
		L = math.ceil(math.sqrt(L))
		R = int(math.sqrt(R))
		cnt = 0
		for i in range(L, R + 1):
			if isprime(i):
				cnt += 1
		return cnt


import math

class Solution:

	def count3DivNums(self, L, R):
		r1 = math.ceil(math.sqrt(L))
		r2 = int(math.sqrt(R))
		if r1 == 1:
			r1 += 1
		ans = 0
		for i in range(r1, r2 + 1):
			flag = True
			for j in range(2, int(math.sqrt(i)) + 1):
				if i % j == 0:
					flag = False
					break
			if flag:
				ans += 1
		return ans


import math

class Solution:

	def count3DivNums(self, L, R):
		primes = []
		for i in range(2, int(math.sqrt(R)) + 1):
			if self.isPrime(i):
				primes.append(i)
		cnt = 0
		for i in primes:
			if i * i >= L and i * i <= R:
				cnt += 1
		return cnt

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


import math

class Solution:

	def prime(self, n):
		if n == 0 or n == 1:
			return False
		if n == 2 or n == 3:
			return True
		if n % 2 == 0 or n % 3 == 0:
			return False
		for i in range(5, int(math.sqrt(n)) + 1, 6):
			if n % i == 0 or n % (i + 2) == 0:
				return False
		return True

	def count3DivNums(self, l, r):
		p = int(math.sqrt(l))
		d = int(math.sqrt(r))
		c = []
		for i in range(p, d + 1):
			if self.prime(i):
				ni = i * i
				if ni > l:
					c.append(i * i)
		return len(c)


class Solution:

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

	def count3DivNums(self, L, R):
		DiViSoRs = 0
		L = int(L ** 0.5 + 1.0)
		R = int(R ** 0.5) + 1
		for x in range(L, R):
			if self.isPrime(x):
				DiViSoRs += 1
		return DiViSoRs


class Solution:

	def sqrt(self, x, flag):
		for i in range(1, x + 1):
			if i * i == x:
				return i
			elif i * i > x:
				if flag == True:
					return i
				return i - 1

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

	def count3DivNums(self, L, R):
		L = 2 if self.sqrt(L, True) < 2 else self.sqrt(L, True)
		R = self.sqrt(R, False)
		c = 0
		for i in range(L, R + 1):
			if self.isprime(i):
				c += 1
		return c


from math import sqrt

class Solution:

	def count3DivNums(self, l, r):
		n = 10 ** 5
		arr = [False for i in range(n)]
		for i in range(2, n):
			for j in range(2 * i, n, i):
				arr[j] = True
		i = 2
		count = 0
		while i * i <= r:
			if i * i >= l:
				if arr[i] == False:
					count += 1
			i += 1
		return count


class Solution:

	def count3DivNums(self, L, R):
		primes = [True for _ in range(int(R ** 0.5) + 1)]
		for i in range(2, len(primes)):
			if primes[i]:
				for j in range(i * i, len(primes), i):
					primes[j] = False
		start = int(L ** 0.5)
		if start ** 2 < L:
			start += 1
		if start == 1:
			start += 1
		count = 0
		for i in range(start, len(primes)):
			if primes[i]:
				count += 1
		return count


import math

class Solution:

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

	def count3DivNums(self, L, R):
		cnt = 0
		low = int(L ** 0.5)
		if low ** 2 < L:
			low += 1
		high = int(R ** 0.5) + 1
		for i in range(low, high):
			if i == 1:
				continue
			if self.prime(i):
				cnt += 1
		return cnt


class Solution:

	def count3DivNums(self, L, R):
		import math
		s = 0
		a = int(math.sqrt(R))
		c = [True] * (a + 1)
		p = 2
		while p * p <= a:
			if c[p] == True:
				for i in range(p * p, a + 1, p):
					c[i] = False
			p = p + 1
		for i in range(2, a + 1):
			if c[i] == True:
				h = i * i
				if h < R and h > L:
					s = s + 1
		return s


import math

class Solution:

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

	def count3DivNums(self, L, R):
		count = 0
		for i in range(math.ceil(math.sqrt(L)), int(math.sqrt(R)) + 1):
			if self.prime(i) == True:
				count += 1
		return count


import math

def isPrime(val):
	if val == 1:
		return 0
	for i in range(2, int(val ** 0.5) + 1):
		if val % i == 0:
			return 0
	return 1

class Solution:

	def count3DivNums(self, L, R):
		Ls = math.ceil(L ** 0.5)
		Rs = int(R ** 0.5)
		count = 0
		for i in range(Ls, Rs + 1):
			if isPrime(i):
				count += 1
		return count