Given two integers L and R find (number of composites - number of primes) between the range L and R (both inclusive).
Example 1:
Input: L = 4, R = 6
Output: 1
Explanation: Composite no. are 4 and 6.
And prime is 5.
Example 2:
Input: L = 4, R = 4
Output: 1
Explanation: There is no prime no. in [L,R]
 
Your Task:
You don't need to read or print anything. Your task is to complete the function Count() which takes L and R as input parameter and returns difference between no. of composites and primes between [L,R].
 
Expected Time Complexity: O(nlog(n)) where n = R - L + 1
Expected Space Complexity: O(n)
 
Constraints:
1 <= L <= R <= 10^{5}

Difficulty: MEDIUM
Tags: Number theory

Dynamic programming
Skill types: Dynamic programming
Expected Time Complexity: O(nlog(n)) where n = R - L + 1
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3



class Solution:

	def Count(self, L, R):

		# Code here

Solutions:
class Solution:

	def Count(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
			else:
				cnt1 += 1
		if L == 1:
			return cnt1 - cnt - 1
		return cnt1 - cnt


class Solution:

	def Count(self, L, R):
		if L == 1:
			L += 1
		b = [1 for i in range(R + 1)]
		for i in range(2, R + 1):
			if b[i] == 1:
				j = 2 * i
				while j <= R:
					b[j] += 1
					j += i
		s = []
		s1 = []
		for i in range(L, R + 1):
			if b[i] == 1:
				s.append(i)
			elif b[i] > 1:
				s1.append(i)
		return len(s1) - len(s)


import math

class Solution:

	def Count(self, L, R):
		r = t = 0
		arr = (R + 1) * [True]
		arr[0] = False
		arr[1] = False
		for i in range(2, int(math.sqrt(R)) + 1):
			for j in range(i + i, R + 1, i):
				arr[j] = False
		for i in range(L, R + 1):
			if arr[i] == True:
				r += 1
			elif arr[i] == False and i != 0 and (i != 1):
				t += 1
		return t - r


import math

class Solution:

	def Count(self, L, R):
		ub = R
		sieve = [True] * (ub + 1)
		sieve[0] = False
		sieve[1] = False
		s = int(math.sqrt(ub))
		for i in range(2, s + 1):
			if sieve[i]:
				for j in range(i + i, ub + 1, i):
					sieve[j] = False
		l = []
		k = []
		for i in range(L, R + 1):
			if sieve[i] == True:
				l.append(i)
			else:
				k.append(i)
		p = set(k)
		p.discard(1)
		return len(p) - len(l)


import math

class Solution:

	def Count(self, L, R):
		l = [True] * (R + 1)
		s = int(math.sqrt(R))
		l[0] = False
		l[1] = False
		for i in range(2, s + 1):
			if l[i]:
				for j in range(i + i, R + 1, i):
					l[j] = False
		pc = 0
		cm = 0
		for i in range(L, len(l)):
			if l[i]:
				if i >= L:
					pc += 1
			elif i != 1:
				cm += 1
		return cm - pc


import math

class Solution:

	def Count(self, L, R):
		if L == R:
			return '1'
		s = int(math.sqrt(R))
		v = (R + 1) * [1]
		for i in range(s + 1):
			if i < 2:
				v[i] = 0
			if v[i]:
				for j in range(i + i, R + 1, i):
					v[j] = 0
		(p, c) = (0, 0)
		if L == 1:
			L = 2
		for i in range(L, len(v)):
			if v[i] == 0:
				c += 1
			else:
				p += 1
		return c - p


import math

class Solution:

	def Count(self, L, R):
		if L == R:
			return 1
		lst1 = []
		lst2 = []
		sieve = [True] * (R + 1)
		sieve[0] = sieve[1] = False
		s = int(math.sqrt(R))
		for i in range(2, s + 1):
			if sieve[i] == True:
				for j in range(i * 2, R + 1, i):
					sieve[j] = False
		if L == 1:
			L = L + 1
		for i in range(L, R + 1):
			if sieve[i] == True:
				lst1.append(i)
			else:
				lst2.append(i)
		return len(set(lst2)) - len(lst1)


import math as m

class Solution:

	def Count(self, L, R):
		s = [True] * (R + 1)
		s[0] = s[1] = False
		for i in range(2, m.ceil(m.sqrt(R)) + 1):
			if s[i]:
				for j in range(i + i, len(s), i):
					s[j] = False
		cnt = 0
		cn = 0
		for i in range(L, R + 1):
			if s[i]:
				cnt += 1
			else:
				cn += 1
		if L == 1:
			return cn - cnt - 1
		return cn - cnt


import math

class Solution:

	def Count(self, L, R):
		array = [True] * (R + 1)
		array[0] = False
		array[1] = False
		sq = int(math.sqrt(R))
		for i in range(2, sq + 1):
			if array[i]:
				for j in range(i + i, R + 1, i):
					array[j] = False
		comp = 0
		prim = 0
		for i in range(L, len(array)):
			if array[i]:
				prim += 1
			else:
				comp += 1
		if L == 1:
			return comp - prim - 1
		else:
			return comp - prim


import math

class Solution:

	def Count(self, L, R):
		sieve = [1] * (R + 1)
		sieve[0] = -1
		sieve[1] = -1
		for i in range(2, int(math.sqrt(R)) + 1):
			if sieve[i]:
				for j in range(i * i, R + 1, i):
					sieve[j] = 0
		x = sieve[L:R + 1]
		return x.count(0) - x.count(1)


import math

class Solution:

	def sieve(self, L, R):
		count = 0
		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
		for p in range(L, R + 1):
			if prime[p]:
				count += 1
		return count

	def Count(self, L, R):
		primes = self.sieve(L, R)
		if L == 1:
			primes = primes - 1
		composites = R - L + 1 - primes
		return composites - primes if L > 1 else composites - primes - 1


ub = int(100000.0)
sieve = [1] * (ub + 1)
sieve[0] = sieve[1] = -1
for i in range(2, int(ub ** 0.5) + 1):
	if sieve[i]:
		for j in range(i * i, ub + 1, i):
			sieve[j] = 0

class Solution:

	def Count(self, L, R):
		x = sieve[L:R + 1]
		return x.count(0) - x.count(1)


import math

class Solution:

	def Count(self, L, R):
		if L == 1 or R == 1:
			total = R - L
		else:
			total = R - L + 1
		sieve = [True] * (R + 1)
		(sieve[0], sieve[1]) = (False, False)
		for i in range(2, int(R ** 0.5) + 1):
			if sieve[i]:
				for j in range(i + i, R + 1, i):
					sieve[j] = False
		count = 0
		for i in range(L, R + 1):
			if sieve[i]:
				count += 1
		comp = total - count
		return comp - count


import math

class Solution:

	def Count(self, L, R):
		p = [True for _ in range(R + 1)]
		p[0] = False
		p[1] = False
		for i in range(2, int(math.sqrt(R)) + 1):
			if p[i] == False:
				continue
			for j in range(i * i, R + 1, i):
				p[j] = False
		prime = 0
		composite = 0
		for i in range(L, R + 1):
			if i == 1:
				continue
			if p[i] == True:
				prime += 1
			else:
				composite += 1
		return composite - prime


def fun(x, n):
	prime = [True for i in range(1, n + 2)]
	p = 2
	prime[0] = False
	prime[1] = False
	while p * p <= n:
		if prime[p] == True:
			for j in range(p * p, n + 1, p):
				prime[j] = False
		p += 1
	(c, d) = (0, 0)
	for k in range(x, n + 1):
		if prime[k] == True:
			d += 1
		elif k != 1:
			c += 1
	return c - d

class Solution:

	def Count(self, L, R):
		return fun(L, R)


class Solution:

	def Count(self, l, r):
		r = r + 1
		c = 0
		p = 0
		a = [1] * r
		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, i):
					a[j] = 0
		for k in range(l, r):
			if k == 1:
				continue
			if a[k] == 0:
				c += 1
			else:
				p += 1
		return c - p


import math

class Solution:

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


class Solution:

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


import math

class Solution:

	def Count(self, L, R):
		if L == 1:
			L = 2
		limit = round(math.sqrt(R))
		arr = [1] * (R + 1)
		arr[0] = arr[1] = 0
		for i in range(2, limit + 1):
			j = 2
			while i * j <= R:
				arr[i * j] = 0
				j += 1
		for i in range(2, R + 1):
			arr[i] += arr[i - 1]
		return R - L + 1 - (arr[R] - arr[L - 1]) - (arr[R] - arr[L - 1])


class Solution:

	def Count(self, l, r):
		size = r
		sieve = [i for i in range(size + 1)]
		for i in range(2, size + 1):
			if sieve[i] == i:
				j = i * 2
				while j < size + 1:
					sieve[j] = i
					j += i
		comps = primes = 0
		for i in range(max(l, 2), r + 1):
			if sieve[i] == i:
				primes += 1
			else:
				comps += 1
		return comps - primes


class Solution:

	def Count(self, L, R):

		def check(n):
			if n < 4:
				return True
			if n % 2 == 0:
				return False
			k = int(n ** 0.5) + 1
			for i in range(3, k, 2):
				if n % i == 0:
					return False
			return True
		c = 0
		t = R - L + 1
		p = 0
		if L == 1:
			L += 1
			t -= 1
		if L == 2:
			p += 1
		if L % 2 == 0:
			L += 1
		for i in range(L, R + 1, 2):
			if check(i):
				p += 1
		return t - 2 * p


import math

class Solution:

	def sieve(self, N):
		l = [0] * (N + 1)
		k = 2
		while k * k <= N:
			if l[k] == 0:
				j = k * k
				for i in range(j, N + 1, k):
					l[i] = 1
			k += 1
		b = []
		for i in range(2, N + 1):
			if l[i] == 0:
				b.append(i)
		return b

	def Count(self, L, R):
		if L < 2:
			L = 2
		flag = [True] * (R - L + 1)
		k = int(R ** 0.5)
		l = self.sieve(k)
		for i in l:
			d = math.ceil(L / i)
			if d == 1:
				d = 2
			while i * d - L < R - L + 1:
				flag[i * d - L] = False
				d += 1
		p = [0, 0]
		for i in range(R - L + 1):
			if flag[i]:
				p[0] += 1
			else:
				p[1] += 1
		return p[1] - p[0]


class Solution:

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


class Solution:

	def Count(self, L, R):

		def isPrime(n):
			k = int(n ** 0.5) + 1
			for i in range(3, k, 2):
				if not n % i:
					return False
			return True
		if (L, R) == (1, 1):
			return 0
		if L == 1:
			L = 2
		(c, t) = (0, R - L + 1)
		if L == 2:
			c = 1
		if L % 2 == 0:
			L += 1
		for i in range(L, R + 1, 2):
			if isPrime(i):
				c += 1
		return t - 2 * c


prime = [True for i in range(0, 10 ** 5 + 1)]
prime[0] = prime[1] = False
for i in range(2, 10 ** 5 + 1):
	if prime[i] == True:
		j = 2 * i
		while j < 10 ** 5 + 1:
			if prime[j] == True:
				prime[j] = False
			j += i

class Solution:

	def Count(self, L, R):
		pcnt = 0
		ccnt = 0
		for num in range(L, R + 1):
			if num == 0 or num == 1:
				continue
			elif prime[num] == True:
				pcnt += 1
			else:
				ccnt += 1
		return ccnt - pcnt


import math
d = {}

class Solution:

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

	def Count(self, L, R):
		com = 0
		pri = 0
		for i in range(max(2, L), R + 1):
			if i in d:
				if d[i] == True:
					pri += 1
				else:
					com += 1
			elif self.isPrime(i):
				pri += 1
			else:
				com += 1
		return com - pri


class Solution:

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


from math import sqrt

class Solution:

	def Count(self, L, R):
		prime = [True] * (R + 1)
		prime[0] = False
		prime[1] = False
		for i in range(2, int(sqrt(R)) + 1):
			if prime[i] == True:
				for j in range(2 * i, R + 1, i):
					prime[j] = False
		pr = 0
		cp = 0
		for i in range(L, R + 1):
			if i == 1:
				continue
			if prime[i] == True:
				pr += 1
			else:
				cp += 1
		return cp - pr


import math

class Solution:

	def generatePrimes(n):
		primes = [True] * n
		primes[0] = primes[1] = False
		for i in range(4, n, 2):
			primes[i] = False
		for i in range(3, int(math.sqrt(n))):
			if primes[i]:
				for j in range(i * i, n, i):
					primes[j] = False
		return primes
	N = 100000
	primes = generatePrimes(N)

	def Count(self, L, R):
		composite = 0
		prime = 0
		for i in range(L, R + 1):
			if self.primes[i]:
				prime += 1
			elif i != 1:
				composite += 1
		return composite - prime


import math

class Solution:

	def Count(self, L, R):
		isPrime = [True for i in range(R + 1)]
		for i in range(2, R + 1):
			if isPrime[i]:
				for j in range(2 * i, R + 1, i):
					isPrime[j] = False
		p = 0
		c = 0
		for i in range(L, R + 1):
			if i == 1:
				continue
			if isPrime[i]:
				p += 1
			else:
				c += 1
		return c - p


class Solution:

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


N = int(100000.0)
dp = [1] * (N + 1)

def sieve():
	i = 2
	dp[1] = 0
	while i * i <= N:
		if dp[i] == 1:
			j = 2
			while i * j <= N:
				dp[i * j] = 0
				j += 1
		i += 1
sieve()

class Solution:

	def Count(self, L, R):
		c = 0
		n = R - L + 1
		for i in range(L, R + 1):
			if dp[i]:
				c += 1
		return n - 2 * c if L > 1 else n - 2 * c - 1


class Solution:

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


import math

def isComposite(n):
	if n <= 1:
		return False
	if n <= 3:
		return False
	if n % 2 == 0 or n % 3 == 0:
		return True
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return True
		i = i + 6
	return False

class Solution:

	def isComposite(n):
		if n <= 1:
			return False
		if n <= 3:
			return False
		if n % 2 == 0 or n % 3 == 0:
			return True
		i = 5
		while i * i <= n:
			if n % i == 0 or n % (i + 2) == 0:
				return True
			i = i + 6
		return False

	def Count(self, L, R):
		comp = 0
		prime = 0
		for i in range(L, R + 1):
			if isComposite(i) and i != 1:
				comp += 1
			elif i != 1:
				prime += 1
		return comp - prime


class Solution:

	def __init__(self):
		self.prime = 0

	def returnPrimes(self, L, R):
		n = R + 1
		primes = [1] * n
		primes[0] = 0
		primes[1] = 0
		for i in range(2, n):
			if i * i > n:
				break
			if primes[i] == 1:
				for j in range(i * i, n, i):
					primes[j] = 0
		for i in range(L, R + 1):
			if primes[i] == 1:
				self.prime += 1

	def Count(self, L, R):
		self.returnPrimes(L, R)
		if L == 1:
			L += 1
		return R - L + 1 - 2 * self.prime


class Solution:

	def Count(self, L, R):
		pri = [0] * (R + 1)
		for i in range(2, R + 1):
			for j in range(i * i, R + 1, i):
				pri[j] = 1
		c = 0
		p = 0
		for i in range(L, R + 1):
			if pri[i] == 1:
				c = c + 1
			if pri[i] == 0:
				p = p + 1
		if L == 1:
			return c - p + 1
		else:
			return c - p


import math

def isprime(n):
	if 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, 6):
		if n % i == 0 or n % (i + 2) == 0:
			return False
	return True

class Solution:

	def Count(self, L, R):
		c = 0
		p = 0
		if L == 1:
			L = 2
		for i in range(L, R + 1):
			if isprime(i):
				p += 1
			else:
				c += 1
		return c - p


class Solution:

	def find(self, L):
		dp = [True] * (L + 1)
		for i in range(2, int((L + 1) ** 0.5) + 1):
			if dp[i]:
				for j in range(i * i, L + 1, i):
					dp[j] = False
		c = 0
		for x in dp[2:]:
			if x:
				c += 1
		return c

	def Count(self, L, R):
		p = self.find(L - 1)
		p1 = self.find(R)
		r = L - 1 - p
		r1 = R - p1
		if L == 1:
			r += 1
		return r1 - r - (p1 - p)


class Solution:

	def Count(self, L, R):
		prime = [1] * (R + 1)
		prime[0] = 0
		prime[1] = 0
		p = 2
		while p * p <= R:
			if prime[p]:
				for i in range(p * p, R + 1, p):
					prime[i] = 0
			p += 1
		count = 0
		for i in range(L, R + 1):
			if prime[i] == 1:
				count += 1
		comp = R - L + 1 - count
		if L == 1 and R == 1:
			return 0
		if L == 1:
			return comp - count - 1
		return comp - count


import math

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

class Solution:

	def Count(self, L, R):
		prime_cnt = 0
		comp_cnt = 0
		if L == 1 and L <= R:
			L += 1
		if L == 2 and L <= R:
			prime_cnt += 1
			L += 1
		if L % 2 == 0:
			L += 1
			comp_cnt += 1
		if (R - L + 1) // 2 > 0:
			comp_cnt += (R - L + 1) // 2
		mult_3 = -1
		for i in range(L, R + 1, 2):
			if mult_3 >= 0:
				mult_3 += 1
				if mult_3 == 3:
					mult_3 = 0
					comp_cnt += 1
					continue
			if is_prime(i):
				prime_cnt += 1
			else:
				comp_cnt += 1
				if mult_3 == -1:
					if i % 3 == 0:
						mult_3 = 0
		return comp_cnt - prime_cnt


MAX = 100000
prefix = [0] * (MAX + 1)

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

def query(L, R):
	return prefix[R] - prefix[L - 1]
buildPrefix()

class Solution:

	def Count(self, L, R):
		val = query(L, R)
		return R - L + 1 - 2 * val if L != 1 else R - L - 2 * val


from math import sqrt

class Solution:

	def Count(self, L, R):
		com = 0
		prime = 0
		is_prime = {}
		for val in range(2, R + 1):
			is_prime[val] = True
		for val in range(2, R + 1):
			if is_prime[val] == True:
				i = val * 2
				while i < R + 1:
					is_prime[i] = False
					i += val
		for val in range(max(L, 2), R + 1):
			if is_prime[val]:
				prime += 1
			else:
				com += 1
		return com - prime


class Solution:

	def Count(self, L, R):
		freq = {}
		for i in range(2, R + 1):
			freq[i] = True
		for i in range(2, R + 1):
			if freq[i] == True:
				j = i * i
				while j <= R:
					freq[j] = False
					j = j + i
		comp = 0
		prime = 0
		for i in range(L, R + 1):
			if i == 1:
				continue
			elif freq[i] == True:
				prime += 1
			else:
				comp += 1
		return comp - prime


class Solution:

	def Count(self, L, R):
		dp = [True] * (R + 1)
		dp[0] = False
		dp[1] = False
		for i in range(2, R // 2):
			if dp[i] == True:
				for j in range(i * 2, R + 1, i):
					dp[j] = False
		cnt = 0
		if L == 1:
			L += 1
		for v in range(L, R + 1):
			if dp[v]:
				cnt -= 1
			else:
				cnt += 1
		return cnt


class Solution:

	def isprime(slef, n):
		if n <= 1:
			return False
		if 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 = i + 6
		return True

	def Count(self, L, R):
		composite_num = 0
		prime_num = 0
		for i in range(L, R + 1):
			if i == 1:
				composite_num -= 1
			if self.isprime(i):
				prime_num += 1
			else:
				composite_num += 1
		return composite_num - prime_num


import math

class Solution:
	ds = {}

	def isprime(self, num):
		if num in self.ds:
			return self.ds[num]
		if num == 2:
			return True
		for b in range(2, math.ceil(math.sqrt(num)) + 1):
			if num % b == 0:
				self.ds[num] = False
				return False
		self.ds[num] = True
		return True

	def Count(self, L, R):
		prim = 0
		comp = 0
		if L == 1:
			L = 2
		for i in range(L, R + 1, 1):
			if self.isprime(i):
				prim += 1
			else:
				comp += 1
		return comp - prim


class Solution:

	def seive(self, L, R):
		count = 0
		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
		for p in range(L, R + 1):
			if prime[p]:
				count += 1
		return count

	def Count(self, L, R):
		if L == R and L % 2 == 0 and (R % 2 == 0):
			return 1
		if L == R and L % 2 != 0 and (R % 2 != 0):
			return -1
		primes = self.seive(L, R)
		if L == 1:
			primes -= 1
		composite = R - L + 1 - primes
		return composite - primes if L > 1 else composite - primes - 1


from math import floor, sqrt

class Solution:

	def is_prime(self, n):
		if 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, floor(sqrt(n)), 6):
			if n % i == 0 or n % (i + 2) == 0:
				return False
		return True

	def Count(self, L, R):
		composite_count = 0
		prime = {k: True for k in range(L, R + 1)}
		p = 2
		total_count = len(prime) - (0 if L > 1 else 1)
		while p * p <= R:
			if p <= L or prime[p] == True:
				for i in range(p * p, R + 1, p):
					if i >= L and prime[i]:
						prime[i] = False
						if i >= L:
							composite_count += 1
			p += 1
		prime_count = total_count - composite_count
		return composite_count - prime_count


from numpy import ones

class Solution:

	def Count(self, L, R):
		N = R + 2
		primes = ones([N])
		primes[0] = primes[1] = 0
		for i in range(2, 1 + int(N ** 0.5)):
			if primes[i]:
				j = i * i
				while j < N:
					primes[j] = 0
					j += i
		(p, c) = (0, 0)
		for i in range(L, R + 1):
			if primes[i]:
				p += 1
			else:
				c += 1
		if L == 1:
			return c - p - 1
		return c - p


class Solution:

	def Count(self, L, R):

		def prime(n):
			if n == 2 or n == 3:
				return True
			elif n % 2 == 0 or n % 3 == 0:
				return False
			else:
				for i in range(5, int(n ** 0.5) + 1, 6):
					if n % i == 0 or n % (i + 2) == 0:
						return False
			return True
		pcnt = 0
		cnt = 0
		if L == 1:
			L = 2
		for i in range(L, R + 1):
			if prime(i):
				pcnt += 1
			else:
				cnt += 1
		return cnt - pcnt


class Solution:

	def Count(self, L, R):
		cnt = 0
		arr = [True] * (R + 1)
		if L == 1:
			L += 1
		for num in range(1, R + 1):
			if arr[num]:
				if num > 1:
					if num >= L:
						cnt += 1
					for i in range(num, R + 1, num):
						arr[i] = False
		return R - L + 1 - 2 * cnt


class Solution:

	def Count(self, L, R):
		prime = [1 for i in range(R + 1)]
		prime[0] = 0
		prime[1] = 0
		for i in range(2, int(pow(R, 0.5)) + 1):
			if prime[i]:
				for j in range(i * i, R + 1, i):
					prime[j] = 0
		count_prime = 0
		count_composite = 0
		for i in range(L, R + 1):
			if prime[i]:
				count_prime += 1
			elif i > 1:
				count_composite += 1
		return count_composite - count_prime


import math

class Solution:

	def Count(self, L, R):
		prime = [-1 for i in range(R + 1)]
		p = 2
		while p * p <= R:
			if prime[p] == -1:
				for i in range(p * p, R + 1, p):
					prime[i] = 1
			p += 1
		l = max(2, L)
		op = sum((prime[i] for i in range(l, R + 1)))
		return op


prime = [1] * (10 ** 5 + 1)
n = 10 ** 5 + 1
prime[0] = 0
prime[1] = 0
for i in range(2, int(n ** 0.5) + 1):
	j = 2
	while j * i < n:
		prime[j * i] = 0
		j += 1

class Solution:

	def Count(self, L, R):
		prim = 0
		composite = 0
		for i in range(L, R + 1):
			if prime[i] == 1:
				prim += 1
			else:
				composite += 1
		if L <= 1:
			composite -= 1
		return composite - prim


from math import sqrt, ceil

class Solution:

	def sieveOfEratosthenes(self, n):
		sieve = [True] * n
		sieve[0] = sieve[1] = False
		for i in range(2, ceil(sqrt(n))):
			if sieve[i]:
				for j in range(i * i, n, i):
					sieve[j] = False
		primes = []
		for i in range(n):
			if sieve[i]:
				primes.append(i)
		return primes

	def Count(self, L, R):
		limit = ceil(sqrt(R))
		primes = self.sieveOfEratosthenes(limit + 1)
		isPrime = [True] * (R - L + 1)
		for i in primes:
			start = max(ceil(L / i) * i, i * i)
			end = R + 1
			step = i
			for j in range(start, end, step):
				isPrime[j - L] = False
		totalPrimes = totalComposites = 0
		for i in range(len(isPrime)):
			if i + L == 1:
				continue
			if isPrime[i]:
				totalPrimes += 1
			else:
				totalComposites += 1
		return totalComposites - totalPrimes


import math

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

class Solution:

	def Count(self, L, R):
		arr = [0] * (R + 1)
		for i in range(2, R + 1):
			if arr[i] == 0:
				arr[i] = i
				for j in range(i * i, R + 1, i):
					arr[j] = i
		(a, b) = (0, 0)
		if L == 1:
			L = 2
		for i in range(L, R + 1):
			if arr[i] == i:
				a += 1
			else:
				b += 1
		return b - a


class Solution:

	def Count(self, L, R):
		arr = [0] * (R + 1)
		for i in range(2, R + 1):
			if arr[i] == 0:
				arr[i] = i
				for j in range(i * i, R + 1, i):
					arr[j] = i
		(a, b) = (0, 0)
		if L == 1:
			L = 2
		for i in range(L, R + 1):
			if arr[i] == i:
				a += 1
			else:
				b += 1
		return b - a


class Solution:

	def Count(self, L, R):
		p = ['True' for j in range(R + 1)]
		k = 2
		while k * k <= R:
			if p[k] == 'True':
				for i in range(k * k, R + 1, k):
					p[i] = 'False'
			k += 1
		if L != 1:
			return p[L:R + 1].count('False') - p[L:R + 1].count('True')
		else:
			return p[L:R + 1].count('False') - p[L:R + 1].count('True') + 1


class Solution:

	def Count(self, L, R):
		p = [0] * (R + 1)
		for r in range(2, int(R ** 0.5) + 1):
			s = 2 * r
			while s <= R:
				p[s] = 1
				s += r
		ans = 0
		if L == 1:
			L += 1
		for i in range(L, R + 1):
			if p[i] == 0:
				ans += 1
		ans2 = R - L + 1 - ans
		return ans2 - ans