Given two numbers L and R(L<R). Count all the prime numbers in the range [L, R].
Example 1:
Input:
L=1,R=10
Output:
4
Explanation:
There are 4 primes in this range, 
which are 2,3,5 and 7.
Example 2:
Input:
L=5,R=10
Output:
2
Explanation:
There are 2 primes in this range, 
which are 5 and 7.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countPrimes() which takes the two integers L and R as input parameters and returns the number of prime numbers in the range [L, R].
Expected Time Complexity:O(RLogLog(R))
Expected Auxillary Space:O(R)
Constraints:
1<=L<R<=2*10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Starter code: #User function Template for python3

class Solution:
    def countPrimes(self,L,R):
        #code here

Solutions:
class Solution:

	def countPrimes(self, L, R):
		primes = [True] * (R + 1)
		primes[0] = False
		primes[1] = False
		for i in range(2, int(math.sqrt(R)) + 1):
			if primes[i] == True:
				for j in range(i * i, R + 1, i):
					primes[j] = False
		cnt = 0
		for i in range(L, R + 1):
			if primes[i] == True:
				cnt += 1
		return cnt


class Solution:

	def countPrimes(self, L, R):
		primes = [1] * (R + 1)
		primes[0] = primes[1] = 0
		p = 2
		while p * p <= R:
			if primes[p]:
				for i in range(p * p, R + 1, p):
					primes[i] = 0
			p += 1
		(cnt, cnt1) = (0, 0)
		for i in range(L, R + 1):
			if primes[i]:
				cnt += 1
		return cnt


from math import *
n = 2 * 10 ** 5 + 1
prime = [1] * n
prime[0] = 0
prime[1] = 0

class Solution:

	def sieve(self):
		sq = int(sqrt(n))
		for i in range(2, sq + 1):
			if prime[i] == 1:
				for j in range(i * i, n, i):
					prime[j] = 0

	def countPrimes(self, L, R):
		c = 0
		self.sieve()
		for i in range(L, R + 1):
			if prime[i]:
				c += 1
		return c


class Solution:

	def countPrimes(self, L, R):
		seive = [1] * (R + 1)
		seive[0] = 0
		seive[1] = 0
		for i in range(2, R + 1):
			if seive[i] == 1:
				for j in range(i * i, R + 1, i):
					seive[j] = 0
		c = 0
		for i in range(L, len(seive)):
			if seive[i] == 1:
				c += 1
		return c


class Solution:

	def countPrimes(self, L, R):
		prime = [1] * (R + 1)
		prime[0] = prime[1] = 0
		c = 0
		for i in range(2, R + 1):
			if prime[i]:
				k = 2 * i
				while k < R + 1:
					prime[k] = 0
					k = k + i
		for i in range(L, R + 1):
			if prime[i]:
				c = c + 1
		return c


class Solution:

	def countPrimes(self, L, R):
		prime = [1] * (R + 2)
		prime[0] = prime[1] = 0
		for i in range(2, R + 1):
			if prime[i] == 1:
				for j in range(i * i, R + 1, i):
					prime[j] = 0
		for i in range(1, R + 1):
			prime[i] += prime[i - 1]
		ans = prime[R] - prime[L - 1]
		return ans


class Solution:

	def countPrimes(self, L, R):
		prime = [0] * (R + 1)
		c = 0
		for i in range(2, len(prime)):
			prime[i] = True
		for i in range(2, int(R ** 0.5) + 1):
			if prime[i]:
				for j in range(i + i, R + 1, i):
					prime[j] = False
		for i in range(L, R + 1):
			if prime[i]:
				c += 1
		return c


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

class Solution:

	def countPrimes(self, L, R):
		a = [1] * (R + 1)
		a[0] = a[1] = 0
		for i in range(2, int(R ** 0.5) + 1):
			if a[i]:
				for j in range(i * i, R + 1, i):
					a[j] = 0
		c = 0
		for i in range(L, R + 1):
			if a[i] == 1:
				c += 1
		return c


class Solution:

	def countPrimes(self, left, right):
		sieve = [True for _ in range(right + 1)]
		sieve[0] = False
		sieve[1] = False
		i = 2
		while i * i <= right:
			for j in range(i * i, right + 1, i):
				sieve[j] = False
			i += 1
		res = 0
		for i in range(left, right + 1):
			if sieve[i] == True:
				res += 1
		return res


import math

class Solution:

	def countPrimes(self, L, R):
		p = [1] * (R + 2)
		p[0] = 0
		p[1] = 0
		for i in range(2, int(math.sqrt(len(p))) + 1):
			if p[i]:
				j = 2 * i
				while j < len(p):
					p[j] = 0
					j += i
		p1 = [p[0]]
		for i in range(1, len(p)):
			p1.append(p1[-1] + p[i])
		return p1[R] - p1[L - 1]


class Solution:

	def countPrimes(self, L, R):
		prime = [True for i in range(R + 1)]
		p = 2
		while p * p <= R:
			if prime[p] == True:
				for i in range(p * p, R + 1, p):
					prime[i] = False
			p += 1
		c = 0
		for i in range(L, R + 1):
			if prime[i]:
				c += 1
		if L < 2:
			return c - 1
		else:
			return c


class Solution:
	m = 2 * 10 ** 5
	primes = [1 for i in range(m + 1)]
	primes[0] = 0
	primes[1] = 0
	p = 2
	while p * p <= m:
		if primes[p]:
			for i in range(p * p, m + 1, p):
				primes[i] = 0
		p += 1

	def countPrimes(self, L, R):
		c = 0
		for i in range(L, R + 1):
			if self.primes[i]:
				c += 1
		return c


class Solution:

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


class Solution:

	def countPrimes(self, L, R):
		n = 200001
		siv = [0] * n
		siv[0] = 1
		siv[1] = 1
		for i in range(2, int(n ** 0.5) + 1):
			if siv[i] == 0:
				for j in range(2 * i, n, i):
					siv[j] = 1
		ans = 0
		for i in range(L, R + 1):
			if siv[i] == 0:
				ans += 1
		return ans


class Solution:

	def countPrimes(self, L, R):
		from math import sqrt
		arr = [1] * (R + 1)
		c = 0
		for i in range(2, int(sqrt(R)) + 1):
			if arr[i] == 1:
				for j in range(i * i, R + 1, i):
					arr[j] = 0
		for i in range(L, R + 1):
			if arr[i] == 1 and i != 1:
				c = c + 1
		return c


class Solution:

	def countPrimes(self, l, r):
		r = r + 1
		a = [1] * r
		a[0] = a[1] = 0
		c = 0
		for i in range(2, int(r ** 0.5) + 1):
			if a[i]:
				for j in range(i * i, r, i):
					a[j] = 0
		for k in range(l, r):
			if a[k] == 1:
				c += 1
		return c


class Solution:

	def countPrimes(self, L, R):
		N = int(2 * 10 ** 5) + 1
		prefix = [0] * N
		primes = [1] * N
		p = 2
		while p * p <= N - 1:
			if primes[p] == 1:
				i = p * 2
				while i <= N - 1:
					primes[i] = 0
					i = i + p
			p += 1
		for i in range(2, N):
			prefix[i] = prefix[i - 1]
			if primes[i] == 1:
				prefix[i] += 1
		return prefix[R] - prefix[L - 1]


class Solution:

	def countPrimes(self, L, R):
		lis = [False for i in range(R + 1)]
		count = 0
		lim = int(math.sqrt(R))
		for i in range(2, lim + 1):
			if not lis[i]:
				for j in range(i * i, R + 1, i):
					lis[j] = True
		if L < 2:
			L = 2
		for i in range(L, R + 1):
			if not lis[i]:
				count += 1
		return count


class Solution:

	def countPrimes(self, L, R):
		if R < 2:
			return 0
		dp = [0] * (R + 1)
		count = 0
		for i in range(2, R + 1):
			if dp[i] == 0:
				if i >= L:
					count += 1
				dp[i * i:R + 1:i] = [1] * len(dp[i * i:R + 1:i])
		return count


from math import sqrt

class Solution:

	def countPrimes(self, L, R):
		isPrime = [True] * (R + 1)
		isPrime[1] = False
		isPrime[0] = False
		count = 0
		for i in range(2, int(sqrt(R)) + 1):
			if isPrime[i] == True:
				for j in range(2 * i, R + 1, i):
					isPrime[j] = False
		for i in range(L, R + 1):
			if isPrime[i] == True:
				count += 1
		return count


class Solution:

	def sieve(self, M, N):
		e = 0
		l = [0] * (N + 1)
		i = 2
		while i * i <= N:
			if l[i] == 1:
				i += 1
				continue
			c = 2
			j = i * i
			for k in range(j, N + 1, i):
				l[k] = 1
			i += 1
		if M < 2:
			M = 2
		for i in range(M, N + 1):
			if l[i] == 0:
				e += 1
		return e

	def countPrimes(self, L, R):
		return self.sieve(L, R)


sieve = [1 for i in range(2 * 10 ** 5 + 1)]
sieve[0] = 0
sieve[1] = 0
for p in range(2, 448):
	if not sieve[p]:
		continue
	for i in range(p * p, 2 * 10 ** 5 + 1, p):
		sieve[i] = 0
for i in range(1, 2 * 10 ** 5 + 1):
	sieve[i] += sieve[i - 1]

class Solution:

	def countPrimes(self, L, R):
		return sieve[R] - sieve[L - 1]


class Solution:

	def countPrimes(self, L, R):
		count = 0
		l = 200001
		siv = [0] * l
		siv[0] = 1
		siv[1] = 1
		for i in range(2, int(math.sqrt(l)) + 1):
			if siv[i] == 0:
				for j in range(2 * i, l, i):
					siv[j] = 1
		for i in range(L, R + 1):
			if siv[i] == 0:
				count += 1
		return count


class Solution:

	def countPrimes(self, L, R):
		prime = [True] * (R + 1)
		prime[1] = False
		for i in range(2, R + 1):
			if prime[i] == True:
				for j in range(i * 2, R + 1, i):
					prime[j] = False
		cnt = 0
		for i in range(L, R + 1):
			if prime[i] == True:
				cnt += 1
		return cnt


class Solution:

	def countPrimes(self, L, R):
		n = R + 1
		if n <= 1:
			return 0
		arr = [1] * (R + 1)
		arr[0] = 0
		arr[1] = 0
		i = 2
		while i < n:
			temp = i
			if arr[i] != 0:
				temp += i
				while temp < n:
					arr[temp] = 0
					temp += i
			i += 1
		return sum(arr[L:R + 1])


class Solution:

	def countPrimes(self, L, n):
		N = n
		arr = [True] * (N + 1)
		arr[0] = False
		arr[1] = False
		for i in range(2, int(n ** 0.5) + 1):
			if arr[i]:
				for j in range(i * i, N + 1, i):
					arr[j] = False
		c = 0
		for i in range(L, n + 1):
			if arr[i]:
				c += 1
		return c
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(L, R) = map(int, input().strip().split(' '))
		ob = Solution()
		ans = ob.countPrimes(L, R)
		print(ans)


class Solution:

	def countPrimes(self, L, R):
		k = R + 1
		isprime = [True] * k
		cnt = 0
		for i in range(2, R + 1):
			if isprime[i]:
				if i >= L and i <= R:
					cnt += 1
				j = i * i
				while j <= R:
					isprime[j] = False
					j += i
		return cnt