Given a number N, print all the composite numbers less than or equal to N. The number should be printed in ascending order.
Example 1:
Input: N = 10
Output: 4, 6, 8, 9, 10
Explaination: From 1 to 10 these are 
the only composite numbers.
Example 2:
Input: N = 6
Output: 4, 6
Explaination: From 1 to 6 these are 
the only composite numbers.
Your Task:
You do not need to read input or print anything. Your task is to complete the function compositeNumbers() which takes N as input parameters and returns a list containing all the composite numbers from 1 to N.
Expected Time Complexity: O(N* sqrt(N))
Expected Auxiliary Space: O(N)
Constraints:
4 ≤ N ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def compositeNumbers(self, N):

        # code here

Solutions:
import math

class Solution:

	def compositeNumbers(self, N):

		def composites(n):
			pl = [True] * (n + 1)
			pl[0] = pl[1] = False
			lim = int(math.sqrt(n)) + 1
			for i in range(2, lim):
				if pl[i]:
					for j in range(i * i, n + 1, i):
						pl[j] = False
			res = []
			for i in range(2, n + 1):
				if not pl[i]:
					res.append(i)
			return res
		return composites(N)


from math import sqrt

class Solution:

	def compositeNumbers(self, n):
		l1 = []
		flag = [True for i in range(n + 1)]
		flag[0] = False
		flag[1] = False
		for i in range(4, n + 1, 2):
			flag[i] = False
		for i in range(3, int(sqrt(n)) + 1):
			if flag[i]:
				for j in range(i * i, n + 1, i):
					if flag[j]:
						flag[j] = False
		for i in range(2, n + 1):
			if not flag[i]:
				l1.append(i)
		return l1


import math

class Solution:

	def seive(self, n):
		primes = [True] * n
		primes[0] = primes[1] = False
		for i in range(4, n, 2):
			primes[i] = False
		x = int(math.sqrt(n)) + 1
		for i in range(3, x):
			for j in range(i * i, n, i):
				primes[j] = False
		return primes

	def compositeNumbers(self, n):
		primes = self.seive(n + 1)
		composites = []
		for (i, p) in enumerate(primes):
			if not p and i != 0 and (i != 1):
				composites.append(i)
		return composites


class Solution:

	def Sieve(self, n, l):
		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
		for p in range(2, n + 1):
			if prime[p] == False:
				l.append(p)

	def compositeNumbers(self, N):
		l = []
		self.Sieve(N, l)
		return l


class Solution:

	def isComposite(self, n):
		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 += 6
		return False

	def compositeNumbers(self, N):
		v = []
		for i in range(3, N + 1):
			if self.isComposite(i):
				v.append(i)
		return v
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		arr = ob.compositeNumbers(N)
		size = len(arr)
		for i in range(size):
			print(arr[i], end=' ')
		print()