Given N find all Sophie Germain Prime numbers less than N . A prime number p is called a sophie prime number if 2p+1 is also a prime number. The number 2p+1 is called a safe prime. 
Example 1:
Input: N = 5
Output: 2 3
Explanation: 2 and 3 are prime no. and 
2*2+1 = 5 and 3*2+1 = 7 are also prime
no.
Example 2:
Input: N = 3
Output: 2
Explanation: 2 is prime number and 2*2+1
= 5 is also a prime number.
 
Your Task:
You don't need to read or print anything your task is to complete the function sophie_primes() which takes N as input parameter and returns a list of all Sophie Germain Prime numbers in increasing order.
 
Expected Time Compelxity: O(N* log(N))
Expected Space Compelxity: O(N)
Constraints:
1 <= N <= 10000

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Starter code: #User function Template for python3

class Solution:
	def sophie_Primes(self, n):
		# Code here

Solutions:
class Solution:

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

	def sophie_Primes(self, n):
		l = []
		for i in range(2, n, 1):
			if self.isprime(i) and self.isprime(2 * i + 1):
				l.append(i)
		return l


import math

def fun(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

class Solution:

	def sophie_Primes(self, n):
		d = []
		for i in range(2, n):
			s = 2 * i + 1
			if fun(s) and fun(i):
				d.append(i)
		return d


class Solution:

	def sophie_Primes(self, n):

		def f(n):
			if n == 0 or n == 1:
				return False
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			return True
		res = []
		for i in range(n):
			if f(i) and f(2 * i + 1):
				res.append(i)
		return res


class Solution:

	def sophie_Primes(self, n):

		def is_prime(num):
			i = 2
			while i * i <= num:
				if num % i == 0:
					return False
				i += 1
			return True
		res = []
		for i in range(2, n):
			if is_prime(i) and is_prime(i * 2 + 1):
				res.append(i)
		return res


import math

def sophiPrime(n):
	num = 2 * n + 1
	for x in range(2, int(math.sqrt(num)) + 1):
		if num % x == 0:
			return False
	return True

def isPrime(num):
	for x in range(2, int(math.sqrt(num)) + 1):
		if num % x == 0:
			return False
	return sophiPrime(num)

class Solution:

	def sophie_Primes(self, n):
		res = []
		for x in range(2, n):
			if isPrime(x):
				res.append(x)
		return res


class Solution:

	def sophie_Primes(self, n):

		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
		prime = [0] * n
		ans = []
		for i in range(2, n):
			prime[i] = i
		for i in range(2, int(n ** 0.5) + 1):
			if prime[i] == i:
				if isPrime(2 * i + 1) == 1:
					ans.append(i)
				for j in range(i * i, n, i):
					prime[j] = 0
		for i in range(int(n ** 0.5) + 1, n):
			if prime[i] == i:
				if isPrime(2 * i + 1) == 1:
					ans.append(i)
		return ans


import math

class Solution:

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

	def sophie_Primes(self, n):
		ans = []
		for i in range(n):
			if self.isPrime(i):
				if self.isPrime(2 * i + 1):
					ans.append(i)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.sophie_Primes(n)
		for _ in ans:
			print(_, end=' ')
		print()


import math

class Solution:

	def checkPrime(self, n):
		if n == 2:
			return True
		for itr in range(2, math.ceil(math.sqrt(n)) + 1):
			if n % itr == 0:
				return False
		return True

	def sophie_Primes(self, n):
		res = []
		for itr in range(2, n):
			if self.checkPrime(itr) and self.checkPrime(2 * itr + 1):
				res.append(itr)
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.sophie_Primes(n)
		for _ in ans:
			print(_, end=' ')
		print()


class Solution:

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

	def sophie_Primes(self, n):
		l = []
		for i in range(2, n):
			if self.ispr(i):
				if self.ispr(2 * i + 1):
					l.append(i)
		return l
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.sophie_Primes(n)
		for _ in ans:
			print(_, end=' ')
		print()


import math

class Solution:

	def sophie_Primes(self, n):
		l = 20002
		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
		lis = []
		for i in range(2, n):
			if siv[i] == False and siv[2 * i + 1] == False:
				lis.append(i)
		return lis


class Solution:

	def sophie_Primes(self, n):
		ans = []

		def isPrime(num):
			if num < 2:
				return False
			for i in range(2, int(num ** 0.5) + 1):
				if num % i == 0:
					return False
			return True
		for i in range(0, n):
			if isPrime(i) and isPrime(2 * i + 1):
				ans.append(i)
		return ans


prime = [True for i in range(10 ** 6 + 1)]

class Solution:

	def genseive(self):
		global prime
		n = 10 ** 6
		if prime[4] == False:
			return
		(prime[0], prime[1]) = (False, False)
		p = 2
		while p * p <= n:
			if prime[p] == True:
				for i in range(p * p, n, p):
					prime[i] = False
			p += 1

	def sophie_Primes(self, n):
		self.genseive()
		l = []
		for i in range(2, n):
			if prime[i] == True and prime[2 * i + 1] == True:
				l.append(i)
		return l


sieve = [True for i in range(10 ** 6 + 1)]

class Solution:

	def gen_sieve(self):
		global sieve
		n = 10 ** 6
		if sieve[4] == False:
			return
		(sieve[0], sieve[1]) = (False, False)
		i = 2
		while i <= n:
			if sieve[i]:
				c = i * i
				while c <= n:
					sieve[c] = False
					c += i
			i += 1

	def sophie_Primes(self, n):
		self.gen_sieve()
		l = []
		for i in range(2, n):
			if sieve[i] == True and sieve[2 * i + 1] == True:
				l.append(i)
		return l


class Solution:

	def sophie_Primes(self, n):
		from math import sqrt
		N = n
		n = n * 2
		l = [0, 0] + [1] * (n + 1)
		k = []
		for i in range(2, int(sqrt(n)) + 1):
			if l[i] == 1:
				for j in range(i * i, n + 1, i):
					l[j] = 0
		for i in range(2, N):
			if l[i] == 1 and l[2 * i + 1] == 1:
				k.append(i)
		return k


import math

class Solution:

	def sophie_Primes(self, n):
		if n == 0 or n == 1:
			return ''
		l = []
		m = []
		s = [True for i in range(n + 1)]
		s[0] = False
		s[1] = False
		for i in range(2, int(math.sqrt(n)) + 1):
			if s[i] == True:
				for j in range(i * i, n, i):
					s[j] = False
		for i in range(len(s)):
			if s[i] == True:
				l.append(i)
		for j in range(len(l) - 1):
			k = 2 * l[j] + 1
			c = 0
			for b in range(2, int(math.sqrt(k)) + 1):
				if k % b == 0:
					c += 1
			if c == 0:
				m.append(l[j])
		return m


class Solution:

	def sophie_Primes(self, n):

		def prime(k):
			if k == 0 or k == 1:
				return 0
			for i in range(2, int(k ** 0.5) + 1):
				if k % i == 0:
					return 0
			return 1
		li = []
		for i in range(1, n):
			if prime(i) and prime(2 * i + 1):
				li.append(i)
		return li


class Solution:

	def sophie_Primes(self, n):
		import math as m

		def isprime(n):
			sq = int(m.sqrt(n))
			for i in range(2, sq + 1):
				if n % i == 0:
					return False
			else:
				return True
		l = []
		for i in range(2, n):
			a = i * 2 + 1
			if isprime(i) and isprime(a):
				l.append(i)
		return l


class Solution:

	def sophie_Primes(self, n):
		import math
		a = []
		prime = [1] * (n + n + 1)
		prime[0] = prime[1] = 0
		for i in range(2, n):
			if prime[i] == 1:
				for j in range(i * i, n + n + 1, i):
					prime[j] = 0
		for i in range(1, n):
			if prime[i] == 1 and prime[2 * i + 1] == 1:
				a.append(i)
		return a


class Solution:

	def sophie_Primes(self, n):

		def sieve(x):
			pri = [1] * x
			(pri[0], pri[1]) = (0, 0)
			i = 2
			while i * i < x:
				if pri[i]:
					for _ in range(i * i, x, i):
						pri[_] = 0
				i += 1
			return pri
		s = sieve(2 * n + 1)
		l = []
		for i in range(n):
			if s[i]:
				p = 2 * i + 1
				if s[p]:
					l.append(i)
		return l


import math

class Solution:

	def primes(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 sophie_Primes(self, n):
		d = []
		for i in range(n):
			if self.primes(i):
				c = i * 2 + 1
				if self.primes(c):
					d.append(i)
		return d


class Solution:

	def sophie_Primes(self, n):

		def generate(n):
			primes = [True] * n
			(primes[0], primes[1]) = (False, False)
			p = 2
			while p * p <= n:
				if primes[p]:
					for _ in range(p * p, n, p):
						if primes[_]:
							primes[_] = False
				p += 1
			return primes
		l = []
		x = generate(100001)
		for i in range(n):
			if x[i]:
				p = 2 * i + 1
				if x[p]:
					l.append(i)
		return l


import math

class Solution:

	def sophie_Primes(self, n):
		l = []
		if n == 0 or n == 1:
			return []

		def pri(u):
			for i in range(2, int(math.sqrt(u)) + 1):
				if u % i == 0:
					return False
			return True
		prime = [1] * n
		(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, i):
					prime[j] = 0
		for i in range(len(prime)):
			if prime[i] == 1 and pri(2 * i + 1):
				l.append(i)
		return l


class Solution:

	def sophie_Primes(self, n):

		def seive(i):
			l = [1 for j in range(i + 1)]
			l[0] = 0
			l[1] = 0
			p = 2
			while p * p <= i:
				if l[p] == 1:
					for k in range(p * p, i + 1, p):
						l[k] = 0
				p += 1
			return l
		i = 20001
		res = seive(i)
		l = []
		for j in range(n):
			if res[j] == 1:
				p = 2 * j + 1
				if p < i and res[p] == 1:
					l.append(j)
		return l


import math

class Solution:

	def sophie_Primes(self, n):

		def isprime(n):
			a = int(math.sqrt(n))
			if n == 0 or n == 1:
				return False
			for i in range(2, a + 1):
				if n % i == 0:
					return False
			return True
		l = []
		for i in range(2, n):
			if isprime(i) and isprime(2 * i + 1):
				l.append(i)
		return l


class Solution:

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


class Solution:

	def sophie_Primes(self, n):

		def prime(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
		k = []
		for i in range(1, n):
			if prime(i) and prime(2 * i + 1):
				k.append(i)
		return k


class Solution:

	def sophie_Primes(self, n):
		c = [True] * (2 * n + 1)
		p = 2
		d = []
		while p * p <= 2 * n + 1:
			if c[p] == True:
				for i in range(p * p, 2 * n + 1, p):
					c[i] = False
			p = p + 1
		for i in range(2, len(c) // 2):
			if c[i] == True and c[2 * i + 1] == True:
				d.append(i)
		return d


class Solution:

	def sophie_Primes(self, n):
		if n == 1 or n == 2:
			return []
		c = []
		import math
		for i in range(2, n):
			p = 0
			for j in range(2, int(math.sqrt(i)) + 1):
				if i % j == 0:
					p = 1
					break
			if p == 0:
				z = 0
				b = int(2 * i + 1)
				for k in range(2, int(math.sqrt(b)) + 1):
					if b % k == 0:
						z = 1
						break
				if z == 0:
					c.append(i)
		return c


import math

class Solution:

	def sophie_Primes(self, n):
		l = []
		for i in range(n):
			if isprime(i) == 1:
				j = 2 * i + 1
				if isprime(j) == 1:
					l.append(i)
		return l

def isprime(n):
	if n == 1 or n == 0:
		return 0
	if n == 2 or n == 3:
		return 1
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return 0
	return 1


from math import sqrt

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

class Solution:

	def sophie_Primes(self, n):
		l = []
		for i in range(2, n):
			if prime(i) == 1 and prime(2 * i + 1) == 1:
				l.append(i)
		return l