A prime number is Super Prime if it is a sum of two primes. Find all the Super Primes upto N
Example 1:
Input:
N = 5
Output: 1
Explanation: 5 = 2 + 3, 5 is the
only super prime
Example 2:
Input:
N = 10 
Output: 2
Explanation: 5 and 7 are super primes
Your Task:  
You don't need to read input or print anything. Your task is to complete the function superPrimes() which takes the N as input and returns the count of super primes.
Expected Time Complexity: O(Nlog(logN))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3

class Solution:

	def superPrimes(self, n):

		# code here

Solutions:
class Solution:

	def superPrimes(self, n):
		p = [0] * (n + 1)
		count = 0
		for i in range(2, int(n ** 0.5) + 1):
			if p[i] == 0:
				for j in range(i * i, n + 1, i):
					p[j] = 1
		for i in range(5, n + 1):
			if p[i] == 0 and p[i - 2] == 0:
				count += 1
		return count


import math

class Solution:

	def superPrimes(self, n):
		ok = [1] * (n + 1)
		ok[0] = ok[1] = 0
		for i in range(2, int(math.sqrt(n + 1)) + 1):
			if ok[i]:
				for j in range(i * i, n + 1, i):
					ok[j] = 0
		ans = 0
		for i in range(5, n + 1):
			if ok[i] and ok[i - 2]:
				ans += 1
		return ans


class Solution:

	def prime(self, n):
		x = [True for i in range(n + 1)]
		p = 2
		while p <= n:
			if x[p] == True:
				for i in range(p * p, n + 1, p):
					x[i] = False
			p += 1
		y = []
		for i in range(2, n + 1):
			if x[i]:
				y.append(i)
		return y

	def superPrimes(self, n):
		x = self.prime(n)
		y = set(x)
		p = 0
		for i in x:
			if i + 2 in y:
				p += 1
		return p


class Solution:

	def superPrimes(self, n):
		p = [1] * (n + 1)
		for i in range(2, (n + 1) // 2):
			if p[i]:
				j = 2
				while i * j < n + 1:
					p[i * j] = 0
					j += 1
		c = 0
		for i in range(5, n + 1):
			if p[i] and p[i - 2]:
				c += 1
		return c


class Solution:

	def superPrimes(self, n):
		primes = [1] * (n + 1)
		for i in range(2, (n + 1) // 2):
			if primes[i]:
				j = 2
				while i * j < n + 1:
					primes[i * j] = 0
					j += 1
		count = 0
		for i in range(5, n + 1):
			if primes[i] and primes[i - 2]:
				count += 1
		return count


class Solution:

	def superPrimes(self, n):
		from math import sqrt, floor
		primes = [True] * (n + 1)
		primes[0] = primes[1] = False
		for i in range(2, floor(sqrt(n)) + 1):
			if not primes[i]:
				continue
			for j in range(i * i, n + 1, i):
				primes[j] = False
		ans = 0
		for i in range(6, n + 2, 6):
			if i - 1 <= n and primes[i - 1] and primes[i - 3]:
				ans += 1
			if i + 1 <= n and primes[i + 1] and primes[i - 1]:
				ans += 1
		return ans


class Solution:

	def isPrime(self, n):
		if n < 2:
			return False
		if n == 2 or n == 3:
			return True
		if n % 2 == 0:
			return False
		if n % 3 == 0:
			return False
		limit = int(n ** 0.5)
		i = 5
		t = 2
		while i <= limit:
			if n % i == 0:
				return False
			i += t
			t = 6 - t
		return True

	def superPrimes(self, n):
		if n < 5:
			return 0
		if n < 7:
			return 1
		count = 1
		i = 7
		while i <= n:
			if self.isPrime(i) and self.isPrime(i - 2):
				count += 1
			i += 6
		return count


class Solution:
	m = 10 ** 5
	sieve = [True for i in range(m + 1)]
	for i in range(2, m + 1):
		if sieve[i]:
			for j in range(i * i, m + 1, i):
				sieve[j] = False

	def superPrimes(self, n):
		l = []
		for i in range(2, n + 1):
			if self.sieve[i]:
				l.append(i)
		c = 0
		for i in l:
			if i + 2 <= n and self.sieve[i + 2]:
				c += 1
		return c


class Solution:

	def seive(self, n):
		prime = [True for i in range(n + 1)]
		p = 2
		while p * p <= n:
			if prime[p] == True:
				for i in range(p * p, n + 1, p):
					prime[i] = False
			p += 1
		a2 = []
		for i in range(2, len(prime)):
			if prime[i] == True:
				a2.append(i)
		return a2

	def superPrimes(self, n):
		count = 0
		a2 = self.seive(n)
		for i in range(len(a2) - 1):
			if a2[i + 1] - a2[i] == 2:
				count += 1
		return count


class Solution:

	def superPrimes(self, n):
		if n < 5:
			return 0
		if n < 7:
			return 1
		isPrime = self.sieveOfEratosthenes(n)
		count = 1
		for i in range(6, n + 1):
			if isPrime[i] and isPrime[i - 2]:
				count += 1
		return count

	def sieveOfEratosthenes(self, n):
		isPrime = [True] * (n + 1)
		isPrime[0] = isPrime[1] = False
		for i in range(2, int(n ** (1 / 2)) + 1):
			if isPrime[i]:
				for j in range(i * i, n + 1, i):
					isPrime[j] = False
		return isPrime


class Solution:

	def superPrimes(self, n):
		if n < 5:
			return 0
		if n < 7:
			return 1
		count = 1
		a = 7
		while a <= n:
			if self.isPrime(a) and self.isPrime(a - 2):
				count += 1
			a += 6
		return count

	def isPrime(self, n):
		if n < 2:
			return False
		if n == 2 or n == 3:
			return True
		if n % 2 == 0:
			return False
		if n % 3 == 0:
			return False
		l = int(n ** 0.5)
		a = 5
		b = 2
		while a <= l:
			if n % a == 0:
				return False
			a += b
			b = 6 - b
		return True


class Solution:

	def superPrimes(self, n):
		ans = 0
		primes = [True for i in range(n + 1)]

		def prime(n):
			i = 2
			primes[0] = False
			primes[1] = False
			while i * i <= n:
				if primes[i] == True:
					for k in range(i + i, n + 1, i):
						primes[k] = False
				i += 1
		prime(n)
		arr = []
		for each in range(len(primes)):
			if primes[each]:
				arr.append(each)
		for num in arr:
			if primes[num]:
				if primes[num - 2]:
					ans += 1
		return ans


def Soe(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

class Solution:

	def superPrimes(self, n):
		if n < 5:
			return 0
		prime = Soe(n)
		prime[0] = False
		prime[1] = False
		c = 0
		for i in range(4, n + 1):
			if prime[i] and prime[i - 2]:
				c += 1
		return c


class Solution:

	def superPrimes(self, n):
		a = [0] * (n + 1)
		for i in range(2, n + 1):
			if a[i] == 0:
				for j in range(2, n // i + 1):
					a[i * j] = 1
		arr = []
		for i in range(2, n + 1):
			if a[i] == 0:
				arr.append(i)
		ans = 0
		a1 = [0] * (n + 1)
		for i in range(1, len(arr)):
			if arr[i] + 2 > n:
				break
			if a[arr[i] + 2] == 0:
				if a1[arr[i] + 2] == 0:
					a1[arr[i] + 2] = 1
					ans += 1
		return ans


class Solution:

	def superPrimes(self, n):
		if n == 5:
			return 1

		def p(N):
			if N <= 2:
				return []
			is_prime = [True] * N
			is_prime[0] = False
			is_prime[1] = False
			for i in range(2, int(N ** 0.5) + 1):
				if is_prime[i]:
					for x in range(i * i, n, i):
						is_prime[x] = False
			return [i for i in range(N) if is_prime[i]]
		z = n + 1
		a = p(z)
		y = a[-1]
		for i in range(2, int(y ** 0.5)):
			if y % i == 0:
				a.pop()
				break
		count = 0
		for i in range(len(a) - 1):
			if a[i] + 2 == a[i + 1]:
				count += 1
		return count


class Solution:

	def superPrimes(self, n):
		p = [True] * (n + 1)
		if n <= 2:
			return 0
		for i in range(2, int(n ** 0.5) + 1):
			if p[i]:
				for j in range(i * 2, n + 1, i):
					p[j] = False
		c = 0
		p = p[2:]
		for i in range(len(p)):
			if i >= 2 and p[i] and p[i - 2]:
				c += 1
		return c


class Solution:

	def superPrimes(self, n):
		ans = 0
		primes = [True for i in range(n + 1)]

		def prime(n):
			i = 2
			primes[0] = False
			primes[1] = False
			while i * i <= n:
				if primes[i] == True:
					for k in range(i + i, n + 1, i):
						primes[k] = False
				i += 1
		prime(n)
		arr = []
		for each in range(len(primes)):
			if primes[each]:
				arr.append(each)
		for num in arr:
			if primes[num]:
				if primes[num - 2]:
					ans += 1
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.superPrimes(n)
		print(ans)


class Solution:

	def superPrimes(self, n):
		count = 0
		primes = [True] * (n + 1)
		primes[0] = primes[1] = False
		for i in range(2, n + 1):
			if primes[i]:
				if primes[i - 2]:
					count += 1
				for j in range(i * i, n + 1, i):
					primes[j] = False
		return count


import math

class Solution:

	def superPrimes(self, n):
		dp = [True] * (n + 1)
		(dp[0], dp[1]) = (False, False)
		for i in range(2, int(math.sqrt(n)) + 1):
			if dp[i] == True:
				for j in range(i * i, n + 1, i):
					dp[j] = False
		c = 0
		for i in range(len(dp) - 2):
			if dp[i] == True and dp[i + 2] == True:
				c += 1
		return c


import math

class Solution:

	def isPrime(self, num):
		if num == 2:
			return 1
		elif num == 1 or num % 2 == 0:
			return 0
		else:
			for i in range(3, int(math.sqrt(num)) + 1, 2):
				if num % i == 0:
					return 0
			return 1

	def superPrimes(self, n):
		if n < 7:
			return 1
		elif n < 13:
			return 2
		else:
			counter = 2
			for i in range(13, n + 1, 2):
				if i % 3 == 0 or i % 5 == 0 or (i - 2) % 3 == 0 or ((i - 2) % 5 == 0) or (i % 7 == 0) or ((i - 2) % 7 == 0):
					pass
				elif self.isPrime(i) and self.isPrime(i - 2):
					counter += 1
			return counter


class Solution:

	def superPrimes(self, n):
		if n < 5:
			return 0
		ans = temp = left = right = 0
		index = 2
		arr = [0] * (n + 1)
		arr[2] = 1
		prime = []
		while index <= n:
			if arr[index] == -1:
				index += 1
			else:
				prime.append(index)
				while index * temp <= n:
					arr[index * temp] = -1
					temp += 1
				temp = 0
				index += 1
		arr = [0] * (n + 1)
		for i in prime:
			if i != 2:
				arr[i] = 1
		for i in prime:
			if 2 + i < len(arr):
				if arr[2 + i] == 1:
					ans += 1
		return ans


class Solution:

	def superPrimes(self, n):

		def makeprime(N):
			visited = [1] * (N + 1)
			primes = {}
			for i in range(2, N + 1):
				if visited[i] == 1:
					primes[i] = 1
					for j in range(i + i, N + 1, i):
						visited[j] = 0
			return primes
		prime = makeprime(n)
		count = 0
		for i in prime:
			if i + 2 in prime:
				count += 1
		return count


class Solution:

	def superPrimes(self, n):
		a = [1] * (n + 1)
		a[0] = a[1] = 0
		for i in range(n + 1):
			if a[i]:
				for j in range(i + i, n + 1, i):
					a[j] = 0
		ans = 0
		for i in range(5, n + 1):
			if a[i] == 1 and a[i - 2] == 1:
				ans += 1
		return ans


N = 10 ** 5 + 5
prime = [0] * N
prime[0] = 1
prime[1] = 1
p = []
for i in range(2, N):
	if prime[i] != 0:
		continue
	for j in range(i * 2, N, i):
		prime[j] = 1
	if prime[i] == 0:
		p.append(i)

class Solution:

	def superPrimes(self, n):
		c = 0
		for j in p:
			if j <= n:
				if prime[j - 2] == 0:
					c += 1
			else:
				break
		return c


class Solution:

	def superPrimes(self, n):
		aux = [True] * (n + 1)
		aux[0] = False
		aux[1] = False
		prime = []
		ans = 0
		for i in range(2, n + 1):
			if aux[i]:
				prime.append(i)
				for j in range(i * i, n + 1, i):
					aux[j] = False
		for i in range(len(prime)):
			if aux[prime[i] - 2]:
				ans += 1
		return ans


class Solution:

	def superPrimes(self, n):
		count = 0
		arr = [True for i in range(n + 1)]
		(arr[0], arr[1]) = (False, False)
		p = 2
		while p * p <= n:
			if arr[p]:
				for i in range(p * p, n + 1, p):
					arr[i] = False
			p += 1
		for i in range(n + 1):
			if arr[i] and arr[i - 2]:
				count += 1
		return count


class Solution:

	def allPrimes(self, n):
		allNumbers = [True for i in range(0, n + 1)]
		for p in range(2, n + 1):
			if not allNumbers[p]:
				continue
			if n < p * p:
				break
			curP = 2 * p
			while curP <= n:
				allNumbers[curP] = False
				curP += p
		allNumbers[0] = False
		allNumbers[1] = False
		primes = [i for i in range(n + 1) if allNumbers[i]]
		return primes

	def superPrimes(self, n):
		primes = self.allPrimes(n)
		result = 0
		for i in range(len(primes) - 1):
			if primes[i + 1] == primes[i] + 2:
				result += 1
		return result


class Solution:

	def superPrimes(self, n):
		prime = [True for i in range(n + 1)]
		p = 2
		while p * p <= n:
			if prime[p] == True:
				for i in range(p * p, n + 1, p):
					prime[i] = False
			p += 1
		last = 3
		count = 0
		for p in range(2, n + 1):
			if prime[p]:
				if p - 2 == last:
					count += 1
				last = p
		return count


from math import sqrt

class Solution:

	def superPrimes(self, n):
		primes = [1] * (n + 1)
		for i in range(2, n + 1):
			if primes[i]:
				j = 2
				while i * j < n + 1:
					primes[i * j] = 0
					j += 1
		count = 0
		for i in range(4, n + 1):
			if primes[i] and primes[i - 2]:
				count += 1
		return count


import bisect

class Solution:

	def superPrimes(self, n):

		def seive(n):
			prime = [True] * (n + 1)
			p = 2
			while p * p <= n:
				for i in range(p * p, n + 1, p):
					prime[i] = False
				p += 1
			final = []
			for i in range(2, n + 1):
				if prime[i]:
					final.append(i)
			return final
		prime = set(seive(n))
		count = 0
		for i in prime:
			if i + 2 in prime:
				count += 1
		return count


import math
import time

class Solution:

	def superPrimes(self, n):
		p_count = 0
		numbers = [1 for _ in range(n)]
		numbers[0] = 0
		for i in range(2, int(math.sqrt(n)) + 1):
			if numbers[i - 1] != 0:
				for j in range(i * i, n + 1, i):
					numbers[j - 1] = 0
		for i in range(5, n + 1):
			if numbers[i - 1] and numbers[i - 3]:
				p_count += 1
		return p_count


class Solution:

	def superPrimes(self, n):
		a = [True for i in range(n + 1)]
		a[0] = False
		a[1] = False
		for i in range(2, n + 1):
			if a[i]:
				for j in range(i * 2, n + 1, i):
					a[j] = False
		c = 0
		for i in range(2, n - 1):
			if a[i] and a[i + 2]:
				c += 1
		return c


class Solution:

	def superPrimes(self, n):
		primes = []
		p = 2
		vals = [val for val in range(0, n + 1)]
		bools = [False for item in range(0, n + 1)]
		count = 0
		while p <= int(n ** (1 / 2)):
			if bools[p] == False:
				for i in range(2 * p, n + 1, p):
					bools[i] = True
				p += 1
			else:
				p += 1
		primes = [vals[item] for item in vals if bools[item] == False][2:]
		for i in range(0, len(primes) - 1):
			if 2 + primes[i] == primes[i + 1]:
				count += 1
		return count


import math

class Solution:

	def superPrimes(self, n):
		prime = [1] * (n + 1)
		prime[0] = 0
		prime[1] = 0
		for i in range(2, n + 1):
			if prime[i] == 1:
				for j in range(i * i, n + 1, i):
					prime[j] = 0
		if n < 4:
			return 0
		count = 0
		for i in range(5, n + 1):
			if prime[i] != 1:
				continue
			odd = i - 2
			if prime[odd] == 1:
				count += 1
		return count


from math import sqrt

class Solution:

	def superPrimes(self, n):
		if n < 5:
			return 0
		if n == 5:
			return 1
		p = [1 for i in range(n + 1)]
		p[0] = p[1] = 0
		for i in range(2, n + 1):
			if p[i] == 1:
				for j in range(i * 2, n + 1, i):
					p[j] = 0
		ans = 0
		for i in range(5, n + 1):
			if p[i] == 1 and p[i - 2] == 1:
				ans += 1
		return ans


import math

class Solution:

	def superPrimes(self, n):
		prime = [1] * (n + 1)
		(prime[0], prime[1]) = (0, 0)
		for i in range(2, int(math.sqrt(n)) + 1):
			if prime[i]:
				for j in range(i * i, n + 1, i):
					prime[j] = 0
		c = 0
		for i in range(3, n - 1):
			if prime[i]:
				if prime[2 + i]:
					c += 1
		return c


class Solution:

	def superPrimes(self, n):
		end = n + 1
		dp = [0] * end
		for i in range(2, end):
			if dp[i] == 0:
				j = i + i
				while j < end:
					dp[j] = 1
					j += i
		cnt = 0
		for i in range(5, end):
			if dp[i] == 0 and dp[i - 2] == 0:
				cnt += 1
		return cnt


class Solution:

	def prime(self, n):
		pri = []
		for i in range(n + 1):
			pri.append(i)
		pri[0] = 0
		pri[1] = 0
		p = 2
		while p * p <= n:
			if p != 0:
				for i in range(p * 2, n + 1, p):
					pri[i] = 0
				p += 1
		return set(pri)

	def superPrimes(self, n):
		count = 0
		prim = self.prime(n)
		for i in prim:
			if i + 2 in prim:
				count += 1
		return count - 1


class Solution:

	def superPrimes(self, n):

		def check(n):
			seive = [True] * (n + 1)
			(seive[0], seive[1]) = (False, False)
			p = 2
			while p * p <= n:
				if seive[p] == True:
					for i in range(p * p, n + 1, p):
						seive[i] = False
				p += 1
			return seive
		count = 0
		ans = check(n)
		for i in range(5, n + 1):
			res = i - 2
			if ans[res] and ans[i]:
				count += 1
		return count


class Solution:

	def superPrimes(self, n):
		a = [True] * (n + 1)
		b = []
		i = 2
		while i * i <= n + 1:
			if a[i]:
				for j in range(2 * i, n + 1, i):
					a[j] = 0
			i += 1
		for i in range(2, n + 1):
			if a[i]:
				b += (i,)
		ans = 0
		for i in range(len(b)):
			f = 0
			for j in range(i + 1, len(b)):
				if b[i] + b[j] > n:
					f = 1
					break
				if a[b[i] + b[j]]:
					ans += 1
			if f:
				break
		return ans


class Solution:

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

	def superPrimes(self, n):
		if n < 5:
			return 0
		if n == 5:
			return 1
		if n == 7:
			return 2
		if n == 13:
			return 3
		count = 3
		prev = 17
		for i in range(19, n + 1, 2):
			if i % 3 != 0 and i % 5 != 0 and self.is_prime(i):
				if prev + 2 == i:
					prev = i
					count += 1
				else:
					prev = i
		return count


import math as m

class Solution:

	def sieve(self, n, l):
		arr = [1] * (n + 1)
		arr[0] = 0
		arr[1] = 0
		for i in range(2, int(m.sqrt(n)) + 1):
			for j in range(i * i, n + 1, i):
				if arr[j] == 1:
					arr[j] = 0
		for i in range(len(arr)):
			if arr[i] == 1:
				l.append(i)

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

	def superPrimes(self, n):
		l = []
		self.sieve(n, l)
		x = 2
		c = 0
		for i in l:
			if self.isprime(abs(2 - i)):
				c += 1
		return c


def seive(n):
	n += 5
	arr = [1] * n
	arr[0] = arr[1] = 0
	for i in range(2, n):
		if arr[i] == 0:
			continue
		for j in range(i * i, n, i):
			arr[j] = 0
	return arr

class Solution:

	def superPrimes(self, n):
		arr = seive(n)
		m = len(arr)
		ans = 0
		for i in range(5, n + 1):
			ans += arr[i] and arr[i - 2]
		return ans


class Solution:

	def superPrimes(self, n):
		isprime = [True] * (n + 1)
		isprime[0] = False
		isprime[1] = False
		total = n - 2
		number = 2
		primes = []
		while number ** 2 <= n and total != 0:
			if isprime[number]:
				primes.append(number)
				for i in range(number * 2, n + 1, number):
					isprime[i] = False
					total = total + 1
			number = number + 1
		for i in range(number, n + 1):
			if isprime[i]:
				primes.append(i)
		count = 0
		for num in primes:
			if isprime[num - 2]:
				count = count + 1
		return count


from itertools import combinations as c

class Solution:

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

	def superPrimes(self, n):
		ans = 0
		primes = [True for i in range(n + 1)]

		def prime(n):
			i = 2
			primes[0] = False
			primes[1] = False
			while i * i <= n:
				if primes[i] == True:
					for k in range(i + i, n + 1, i):
						primes[k] = False
				i += 1
		prime(n)
		arr = []
		for each in range(len(primes)):
			if primes[each]:
				arr.append(each)
		for num in arr:
			if primes[num]:
				if primes[num - 2]:
					ans += 1
		return ans