Given two integers L and R, write a program that finds the count of numbers having prime number of set bits in their binary representation in the range [L, R].
Example 1:
Input: L = 6, R = 10
Output: 4
Explanation: 6, 7, 9, 10 having
prime set bits between 6 and 10. 
Example 2:
Input: L = 10, R = 15
Output: 5
Explanation: 10, 11, 12, 13, 14 having
prime set bits between 10 and 15.
Your Task:  
You dont need to read input or print anything. Complete the function primeSetBits() which takes L and R as input parameter and returns the count of numbers having prime number of set bits in their binary representation.
Expected Time Complexity: O(nlog(n)sqrt(n))
Expected Auxiliary Space: O(1)
Constraints:
1 <= L <= R <=1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Starter code: #User function Template for python3
class Solution:
	def primeSetBits(self, L, R):
		# code here


Solutions:
class Solution:

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

	def primeSetBits(self, L, R):
		d = 0
		for i in range(L, R + 1, 1):
			s = str(bin(i))
			c = int(s.count('1'))
			if self.isprime(c):
				d += 1
		return d


class Solution:

	def primeSetBits(self, L, R):

		def popcount(i):
			return bin(i)[2:].count('1')
		count = 0
		for j in range(L, R + 1):
			if popcount(j) in [2, 3, 5, 7, 11, 13, 17, 19]:
				count += 1
		return count


class Solution:

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

	def primeSetBits(self, L, R):
		count = 0
		for i in range(L, R + 1):
			p = bin(i).count('1')
			if self.isPrime(p):
				count += 1
		return count


class Solution:

	def primeSetBits(self, L, R):

		def setBit(n):
			setbit = 0
			while n:
				setbit += n & 1
				n >>= 1
			return setbit

		def prime(n):
			if n < 2:
				return False
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		ans = 0
		for n in range(L, R + 1):
			sb = setBit(n)
			if prime(sb):
				ans += 1
		return ans


class Solution:

	def primeSetBits(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
		ans = 0
		for i in range(L, R + 1):
			if sieve[sum((x == '1' for x in bin(i)))]:
				ans += 1
		return ans


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

class Solution:

	def primeSetBits(self, L, R):
		count = 0
		for i in range(L, R + 1):
			if checkprime(list(bin(i)[2:]).count('1')):
				count += 1
		return count


import math as m

class Solution:

	def primeSetBits(self, L, R):

		def prime(n):
			if n == 0 or n == 1:
				return False
			k = round(m.sqrt(n)) + 1
			for i in range(2, k):
				if n % i == 0:
					return False
			return True
		res = 0
		for i in range(L, R + 1):
			cnt = 0
			while i:
				if i & 1 == 1:
					cnt += 1
				i = i >> 1
			if prime(cnt):
				res += 1
		return res


class Solution:

	def primeSetBits(self, L, R):
		prime = [2, 3, 5, 7]
		cnt = 0
		for i in range(L, R + 1):
			if bin(i).count('1') in prime:
				cnt += 1
		return cnt


class Solution:

	def primeSetBits(self, L, R):

		def isPrime(n):
			if n < 2:
				return False
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		count = 0
		for i in range(L, R + 1):
			set_bits = bin(i).count('1')
			if isPrime(set_bits):
				count += 1
		return count


import math

class Solution:

	def primeSetBits(self, L, R):

		def isprime(num):
			if num < 2:
				return False
			if num < 4:
				return True
			if num % 2 == 0 or num % 3 == 0:
				return False
			for i in range(5, int(math.sqrt(num)) + 1, 6):
				if num % i == 0 or num % (i + 2) == 0:
					return False
			return True
		res = 0
		for i in range(L, R + 1):
			bits = bin(i)[2:]
			cnt = 0
			for bit in bits:
				if bit == '1':
					cnt += 1
			if cnt > 1:
				if isprime(cnt):
					res += 1
		return res


class Solution:

	def primeSetBits(self, L, R):

		def p(n):
			if n == 0 or n == 1:
				return False
			s = int(n ** 0.5)
			for i in range(2, s + 1):
				if n % i == 0:
					return False
			return True
		s = 0
		for i in range(L, R + 1):
			b = bin(i)[2:]
			c = b.count('1')
			if p(c):
				s += 1
		return s


import math

class Solution:

	def primeSetBits(self, L, R):
		l = 1001
		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
		count = 0
		for i in range(L, R + 1):
			m = i
			c = 0
			while m != 0:
				m = m & m - 1
				c += 1
			if siv[c] == 0:
				count += 1
		return count


import math

class Solution:

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

	def primeSetBits(self, L, R):
		ans = 0
		for i in range(L, R + 1):
			temp = bin(i).replace('0b', '')
			j = temp.count('1')
			if self.check_prime(j):
				ans += 1
		return ans


class Solution:

	def primeSetBits(self, L, R):

		def isPrime(num):
			if num < 2:
				return 0
			for i in range(2, int(num ** 0.5) + 1):
				if num % i == 0:
					return 0
			return 1
		ans = 0
		for i in range(L, R + 1):
			binary = bin(i)[2:]
			cnt = binary.count('1')
			if isPrime(cnt) == 1:
				ans += 1
		return ans


class Solution:

	def primeSetBits(self, L, R):
		arr = []
		for d in range(L, R + 1):
			bit = bin(d)[2:]
			summ = 0
			for b in str(bit):
				if b == '1':
					summ = summ + 1
			if summ in [2, 3, 5, 7, 11, 13, 17, 19]:
				arr.append(d)
		return len(arr)


class Solution:

	def primeSetBits(self, L, R):
		d = set((val for val in [2, 3, 5, 7, 11]))
		ans = 0
		for i in range(L, R + 1):
			n = i
			c = 0
			while n:
				c += 1
				n = n & n - 1
			if c in d:
				ans += 1
		return ans


def isprime(x):
	if x <= 1:
		return 0
	else:
		for i in range(2, x):
			if x % i == 0:
				return 0
		return 1

class Solution:

	def primeSetBits(self, L, R):
		l = []
		for i in range(L, R + 1):
			c = 0
			while i:
				c = c + (i & 1)
				i = i >> 1
			l.append(c)
		d = 0
		for i in l:
			if isprime(i):
				d = d + 1
		return d


class Solution:

	def primeSetBits(self, l, r):
		d = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
		ans = 0
		for i in range(l, r + 1):
			k = bin(i)[2:].count('1')
			if k in d:
				ans += 1
		return ans


class Solution:

	def primeSetBits(self, L, R):
		l = [1 for i in range(R + 1)]
		p = 2
		l[0] = 0
		l[1] = 0
		while p * p <= R:
			if l[p] == 1:
				for i in range(p * p, R + 1, p):
					l[i] = 0
			p += 1
		c = 0
		for i in range(L, R + 1):
			s = bin(i)
			if l[s.count('1')] == 1:
				c += 1
		return c


class Solution:

	def primeSetBits(self, L, R):
		a = [1] * (R + 3)
		a[0] = a[1] = 0
		i = 2
		while i * i <= R:
			for j in range(i * i, R + 1, i):
				a[j] = 0
			i += 1
		cnt = 0
		for i in range(L, R + 1):
			s = int(bin(i)[2:])
			c = 0
			while s:
				r = s % 10
				s = s // 10
				if r:
					c += 1
			cnt += a[c]
		return cnt


class Solution:

	def primeSetBits(self, L, R):

		def prime(n):
			if n > 1:
				for k in range(2, n):
					if n % k == 0:
						return 0
				return 1
			else:
				return 0
		l = []
		for i in range(L, R + 1):
			l.append(bin(i).replace('0b', '').count('1'))
		li = 0
		for j in l:
			if prime(j):
				li += 1
		return li


class Solution:

	def primeSetBits(self, L, R):
		import math
		t = 0
		for i in range(L, R + 1):
			c = []
			z = i
			while z > 0:
				a = z % 2
				c.append(a)
				z = z // 2
			a = c.count(1)
			if a == 1:
				continue
			p = 0
			for j in range(2, int(math.sqrt(a)) + 1):
				if a % j == 0:
					p = 1
			if p == 0:
				t += 1
		return t


class Solution:

	def primeSetBits(self, L, R):

		def isPrime(N):
			if N == 1:
				return 0
			elif N == 2:
				return 1
			else:
				for i in range(2, int(N ** 0.5) + 1):
					if N % i == 0:
						return 0
				return 1
		c = 0
		for i in range(L, R + 1):
			x = bin(i)[2:]
			y = x.count('1')
			if isPrime(y):
				c += 1
		return c


class Solution:

	def isp(self, 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 primeSetBits(self, L, R):
		count = 0
		for i in range(L, R + 1):
			to = str(bin(i))
			co1 = to.count('1')
			if self.isp(co1) == True:
				count += 1
		return count


def isprime(n):
	if n <= 1:
		return 0
	for i in range(2, n):
		if n % i == 0:
			return 0
	return 1

def count_one(n):
	return bin(n).count('1')

class Solution:

	def primeSetBits(self, L, R):
		ans = 0
		for n in range(L, R + 1):
			ans += isprime(count_one(n))
		return ans


class Solution:

	def primeSetBits(self, L, R):
		(count, co) = (0, 0)

		def prime(c):
			if c == 2:
				return True
			if c % 2 == 0 or c == 1:
				return False
			for i in range(3, int(c / 3) + 1, 2):
				if c % i == 0:
					return False
			return True
		for i in range(L, R + 1):
			x = bin(i)[2:]
			for j in x:
				if j == '1':
					count += 1
			if prime(count):
				co += 1
			count = 0
		return co


class Solution:

	def prime(self, n):
		if n == 1:
			return 0
		for i in range(2, n // 2 + 1):
			if n % i == 0:
				return 0
		return 1

	def primeSetBits(self, L, R):
		m = 0
		for i in range(L, R + 1):
			s = str(bin(i))
			k = s.count('1')
			if self.prime(k):
				m = m + 1
		return m


class Solution:

	def primeSetBits(self, L, R):
		n = 1000 + 1
		arr = [True] * n
		arr[0] = False
		arr[1] = False
		i = 2
		while i < n:
			if arr[i]:
				for j in range(i * i, n, i):
					arr[j] = False
			i += 1
		c = 0
		lis = []
		count = 0
		for k in range(L, R + 1):
			x = bin(k)
			c = x.count('1')
			if arr[c] == 1:
				count += 1
		return count


import math

class Solution:

	def primeSetBits(self, L, R):
		prime = [True] * 33
		prime[0] = prime[1] = False
		for i in range(2, int(math.sqrt(32)) + 1):
			if prime[i]:
				j = i
				while i * j <= 32:
					prime[i * j] = False
					j += 1
		c = 0
		for i in range(L, R + 1):
			setbits = 0
			while i != 0:
				if i & 1 == 1:
					setbits += 1
				i = i >> 1
			if prime[setbits] == True:
				c += 1
		return c


class Solution:

	def primeSetBits(self, L, R):
		final = 0
		sieve = [1] * 100005
		sieve[0] = 0
		sieve[1] = 0
		for i in range(2, int(100005 ** 0.5) + 1):
			if sieve[i] == 1:
				for j in range(i * i, 100005, i):
					if sieve[j] == 1:
						sieve[j] = 0
		for i in range(L, R + 1):
			count = 0
			while i:
				count += i & 1
				i = i >> 1
			if sieve[count] == 1:
				final += 1
		return final


class Solution:

	def primeSetBits(self, L, R):
		count = 0
		a = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
		for num in range(L, R + 1, 1):
			c = list(bin(num).replace('0b', ''))
			countSet = c.count('1')
			if countSet in a:
				count += 1
		return count


class Solution:

	def isprime(self, num):
		a = 0
		for i in range(1, num + 1):
			if num % i == 0:
				a += 1
		if a > 2 or a == 1:
			return False
		else:
			return True

	def primeSetBits(self, L, R):
		count = 0
		for i in range(L, R + 1):
			x = bin(i)
			x = x[2:]
			c = 0
			for i in x:
				if i == '1':
					c += 1
			if self.isprime(c) == True:
				count += 1
		return count


class Solution:

	def primeSetBits(self, L, R):
		count = 0
		for i in range(L, R + 1):
			n = bin(i).replace('0b', '')
			if prime(n):
				count = count + 1
		return count

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


class Solution:

	def primeSetBits(self, L, R):
		count = flag = prime = 0
		for i in range(L, R + 1):
			count = bin(i).count('1')
			flag = 0
			for j in range(1, count):
				if count % j == 0:
					flag += 1
			if flag == 1:
				prime += 1
		return prime