Given a number N, calculate the prime numbers up to N using Sieve of Eratosthenes.  
Example 1:
Input:
N = 10
Output:
2 3 5 7
Explanation:
Prime numbers less than equal to N 
are 2 3 5 and 7.
Example 2:
Input:
N = 35
Output:
2 3 5 7 11 13 17 19 23 29 31
Explanation:
Prime numbers less than equal to 35 are
2 3 5 7 11 13 17 19 23 29 and 31.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sieveOfEratosthenes() which takes an integer N as an input parameter and return the list of prime numbers less than equal to N.
Expected Time Complexity: O(NloglogN)
Expected Auxiliary Space: O(N)
Constraints:
1<= N <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3



class Solution:

    def sieveOfEratosthenes(self, N):

    	#code here 

Solutions:
class Solution:

	def sieveOfEratosthenes(self, N):
		prime = [True] * (N + 1)
		prime[0] = False
		prime[1] = False
		for i in range(2, N + 1):
			j = i * 2
			while j < N + 1 and prime[i]:
				prime[j] = False
				j = j + i
		ans = []
		for p in range(N + 1):
			if prime[p]:
				ans.append(p)
		return ans


class Solution:

	def sieveOfEratosthenes(self, n):
		primes = [1] * (n + 1)
		primes[0] = primes[1] = 0
		for i in range(2, int(n ** 0.5) + 1):
			j = 2 * i
			for j in range(j, n + 1, i):
				primes[j] = 0
		arr = []
		for i in range(2, n + 1):
			if primes[i] == 1:
				arr.append(i)
		return arr


class Solution:

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


class Solution:

	def sieveOfEratosthenes(self, N):
		primes = [1] * (N + 1)
		primes[0] = 0
		primes[1] = 0
		for i in range(2, N + 1):
			if primes[i] == 1:
				for j in range(i + i, N + 1, i):
					primes[j] = 0
		op = []
		for i in range(N + 1):
			if primes[i] == 1:
				op.append(i)
		return op


from math import *
n = 10 ** 4
prime = [1] * n

def generate_seive():
	sq = int(sqrt(n))
	prime[0] = 0
	prime[1] = 0
	for i in range(2, sq + 1):
		if prime[i] == 1:
			for j in range(i * i, n, i):
				prime[j] = 0

class Solution:

	def sieveOfEratosthenes(self, N):
		generate_seive()
		e = []
		for i in range(2, N + 1):
			if prime[i] == 1:
				e.append(i)
		return e


class Solution:

	def sieveOfEratosthenes(self, N):
		seen = [False] * (N + 1)
		arr = []
		for num in range(2, N + 1):
			if seen[num]:
				continue
			arr.append(num)
			for i in range(num ** 2, N + 1, num):
				seen[i] = True
		return arr


class Solution:

	def sieveOfEratosthenes(self, N):
		u = []
		pr = [True] * (N + 1)
		p = 2
		while p * p <= N:
			if pr[p] == True:
				for i in range(p * p, N + 1, p):
					pr[i] = False
			p += 1
		for x in range(2, N + 1):
			if pr[x] == True:
				u.append(x)
		return u


class Solution:

	def sieveOfEratosthenes(self, N):
		numbers = [True for _ in range(0, N + 1)]
		res = []
		for i in range(2, N + 1):
			if numbers[i] == False:
				continue
			res.append(i)
			for j in range(i, N + 1, i):
				numbers[j] = False
		return res


class Solution:

	def sieveOfEratosthenes(self, N):
		primes = [True] * (N + 1)
		prime = 2
		while prime <= N ** 0.5:
			for i in range(prime ** 2, N + 1, prime):
				primes[i] = False
			prime += 1
			while prime < N and (not primes[prime]):
				prime += 1
		ans = []
		for i in range(2, N + 1):
			if primes[i]:
				ans.append(i)
		return ans


from math import sqrt

class Solution:

	def sieveOfEratosthenes(self, N):
		is_prime = [True] * (N + 1)
		is_prime[0] = is_prime[1] = False
		for i in range(2, int(sqrt(N) + 1)):
			if is_prime[i]:
				for j in range(i * i, N + 1, i):
					is_prime[j] = False
		return list(filter(lambda x: is_prime[x], range(2, N + 1)))


class Solution:

	def sieveOfEratosthenes(self, N):
		primes = {}
		for i in range(2, N + 1):
			primes[i] = True
		i = 2
		while i <= N:
			if primes[i]:
				j = i * i
				while j <= N:
					primes[j] = False
					j = j + i
			i += 1
		result = []
		for k in primes:
			if primes[k]:
				result.append(k)
		return result


class Solution:

	def sieveOfEratosthenes(self, N):
		indices = []
		if N <= 1:
			return indices
		output = [True] * (N + 1)
		output[0] = False
		output[1] = False
		for i in range(2, N + 1):
			if output[i] == True:
				j = i * 2
				while j <= N:
					output[j] = False
					j += i
		indices = [i for (i, v) in list(enumerate(output)) if v == True]
		return indices


class Solution:

	def sieveOfEratosthenes(self, n: int):

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


class Solution:

	def sieveOfEratosthenes(self, N):
		if N <= 1:
			return False
		isPrime = [True] * (N + 1)
		ans = []
		i = 2
		while i <= N:
			if isPrime[i]:
				ans.append(i)
				for j in range(i * i, N + 1, i):
					isPrime[j] = False
			i += 1
		return ans


class Solution:

	def sieveOfEratosthenes(self, n):
		ans = []
		prime = [True for i in range(0, n + 1)]
		prime[0] = prime[1] = False
		for x in range(2, n + 1):
			if prime[x] == True:
				ans.append(x)
				multiple = x + x
				while multiple <= n:
					prime[multiple] = False
					multiple = multiple + x
		return ans


class Solution:

	def sieveOfEratosthenes(self, n):
		ans = []
		nums = list(range(1, n + 1))
		i = 1
		while i < n:
			if nums[i] == 0:
				i += 1
				continue
			ans.append(nums[i])
			x = 2
			m = nums[i] * x
			while m <= n:
				nums[m - 1] = 0
				x += 1
				m = nums[i] * x
			i += 1
		return ans


class Solution:

	def sieveOfEratosthenes(self, N):
		import math
		lis = [True for i in range(N + 1)]
		lis[1] = False
		lis[0] = False
		for i in range(2, int(math.sqrt(N)) + 1, 1):
			j = 2 * i
			for j in range(j, N + 1, i):
				lis[j] = False
		ans = []
		for i in range(2, N + 1):
			if lis[i] == True:
				ans.append(i)
		return ans


class Solution:

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


class Solution:

	def sieveOfEratosthenes(self, N):
		lst = list(range(2, N + 1))
		p = 2
		while p * p <= N:
			for i in range(p - 2, N - N % p, p):
				if lst[i] != p and lst[i] % p == 0:
					lst[i] = 0
			p = self.findNextPrimeNo(p + 1, N)
		lst = filter(lambda x: x != 0, lst)
		return lst

	def findNextPrimeNo(self, c, n):
		for i in range(c, n):
			if i == 2:
				return 2
			for j in range(2, round(i ** 0.5) + 1):
				if i % j == 0:
					break
				if j == round(i ** 0.5):
					return i
		return -1


class Solution:

	def sieveOfEratosthenes(self, n):
		arr = [1] * (n + 1)
		for i in range(2, n + 1):
			if arr[i] == 1:
				for j in range(i * i, n + 1, i):
					arr[j] = 0
		index = 0
		for k in range(2, n + 1):
			if arr[k] == 1:
				arr[index] = k
				index += 1
		return arr[:index]


class Solution:

	def sieveOfEratosthenes(self, N):
		arr = [True] * (N + 1)
		arr[0] = False
		arr[1] = False
		for i in range(2, N + 1):
			if arr[i] != True:
				continue
			for j in range(i, N + 1, i):
				if j == i:
					continue
				arr[j] = False
		ret = []
		for i in range(N + 1):
			if arr[i] == True:
				ret.append(i)
		return ret


class Solution:

	def sieveOfEratosthenes(self, N):
		n = N
		arr = [0 for i in range(n + 1)]
		i = 4
		while i <= n:
			arr[i] = 1
			i = i + 2
		for i in range(3, n + 1, 2):
			x = i * i
			while x <= n:
				arr[x] = arr[x] + 1
				x = x + i
		ans = []
		for i in range(2, n + 1):
			if arr[i] == 0:
				ans.append(i)
		return ans


class Solution:

	def sieveOfEratosthenes(self, N):
		res = []
		l = [True] * (N + 1)
		p = 2
		while p * p <= N:
			if l[p] == True:
				for i in range(p * p, N + 1, p):
					l[i] = False
			p += 1
		for i in range(2, N + 1):
			if l[i]:
				res.append(i)
		return res


class Solution:

	def sieveOfEratosthenes(self, N):
		ans = []
		prime = [1 for i in range(N + 1)]
		prime[0] = prime[1] = 0
		for i in range(2, int(N ** 0.5) + 1):
			j = 2 * i
			for j in range(j, N + 1, i):
				prime[j] = 0
		for i in range(2, N + 1):
			if prime[i] == 1:
				ans.append(i)
		return ans


class Solution:

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

	def sieveOfEratosthenes(self, N):
		l = []
		for i in range(2, N + 1):
			if self.checkprime(i):
				l.append(i)
		return l


class Solution:

	def sieveOfEratosthenes(self, N):
		arr = [0 for _ in range(N + 1)]
		for num in range(2, len(arr)):
			if arr[num] == 0:
				for i in range(num * num, len(arr), num):
					arr[i] = 1
		prime = []
		for i in range(2, len(arr)):
			if arr[i] == 0:
				prime.append(i)
		return prime


class Solution:

	def sieveOfEratosthenes(self, N):
		lst = []
		arr = [True for i in range(N + 1)]
		p = 2
		while p <= N:
			if arr[p] == True:
				for j in range(p * p, N + 1, p):
					arr[j] = False
			p += 1
		for i in range(2, N + 1):
			if arr[i] == True:
				lst.append(i)
		return lst


class Solution:

	def sieveOfEratosthenes(self, n):
		primes = [True] * (n + 1)
		primes[0] = False
		primes[1] = False
		i = 2
		while i * i <= n:
			if primes[i]:
				for j in range(i * 2, n + 1, i):
					primes[j] = False
			i += 1
		res = []
		for i in range(n + 1):
			if primes[i]:
				res.append(i)
		return res


import math

class Solution:

	def sieveOfEratosthenes(self, N):
		l1 = list(range(2, N + 1))
		for i in range(2, int(math.sqrt(N)) + 1):
			if i in l1:
				l1 = list(filter(lambda x: x % i, l1))
				l1.append(i)
		l1.sort()
		return l1


class Solution:
	a = 2

	def f_p(self, x, g):
		if self.a ** 2 > g:
			return x
		op = []
		for iin in x:
			if iin % self.a != 0:
				op.append(iin)
			elif iin == self.a:
				op.append(iin)
		self.a += 1
		return self.f_p(op, g)

	def sieveOfEratosthenes(self, N):
		cf = []
		for ggb in range(2, N + 1):
			cf.append(ggb)
		return self.f_p(cf, N)


class Solution:

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


import math

class Solution:

	def sieveOfEratosthenes(self, N):
		t = []
		x = (N + 1) * [True]
		x[0] = False
		x[1] = False
		for i in range(2, int(math.sqrt(N)) + 1):
			for j in range(i + i, N + 1, i):
				x[j] = False
		for i in range(len(x)):
			if x[i] == True:
				t.append(i)
		return t


class Solution:

	def sieveOfEratosthenes(self, N):
		import math
		ub = N
		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
		ans = []
		for i in range(len(sieve)):
			if sieve[i] == True:
				ans.append(i)
		return ans


class Solution:

	def sieveOfEratosthenes(self, N):
		sieve = [True for _ in range(N + 1)]
		sieve[0] = False
		sieve[1] = False
		i = 2
		res = []
		while i * i <= N:
			if sieve[i]:
				for j in range(i * i, N + 1, i):
					sieve[j] = False
			i += 1
		for i in range(N + 1):
			if sieve[i]:
				res.append(i)
		return res


class Solution:

	def sieveOfEratosthenes(self, N):
		primes = [1] * (N + 1)
		primes[0] = primes[1] = 0
		for x in range(2, N + 1):
			if primes[x] == 1:
				y = x * x
				while y <= N:
					primes[y] = 0
					y += x
		ans = []
		for x in range(N + 1):
			if primes[x] == 1:
				ans.append(x)
		return ans


class Solution:

	def sieveOfEratosthenes(self, n):

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


class Solution:

	def sieveOfEratosthenes(self, N):
		b = [True for i in range(N + 1)]
		for i in range(2, N // 2):
			if b[i]:
				j = 2 * i
				while j <= N:
					b[j] = False
					j += i
		s = []
		for i in range(2, N + 1):
			if b[i]:
				s.append(i)
		return s


import math

class Solution:

	def sieveOfEratosthenes(self, N):
		s = [True] * (N + 1)
		s[0] = False
		s[1] = False
		a = int(math.sqrt(N))
		for i in range(2, a + 1):
			for j in range(i + i, N + 1, i):
				s[j] = False
		l = []
		for i in range(len(s)):
			if s[i] == True:
				l.append(i)
		return l


import math

def isPrime(N):
	if N <= 1:
		return False
	else:
		for i in range(2, int(math.sqrt(N) + 1)):
			if N % i == 0:
				return False
		return True

class Solution:

	def sieveOfEratosthenes(self, N):
		primes = []
		for i in range(2, N + 1):
			if isPrime(i) == True:
				primes.append(i)
		return primes


class Solution:

	def sieveOfEratosthenes(self, N):
		a = []
		for num in range(1, N + 1):
			if num > 1:
				for i in range(2, int(num ** 0.5) + 1):
					if num % i == 0:
						break
				else:
					a.append(num)
		return a


import math

class Solution:

	def sieveOfEratosthenes(self, N):
		a = [1] * (N + 1)
		a[0] = 0
		a[1] = 0
		b = []
		s = int(math.sqrt(N))
		for i in range(2, s + 1):
			if a[i]:
				for j in range(2 * i, N + 1, i):
					a[j] = 0
		for i in range(N + 1):
			if a[i] == 1:
				b.append(i)
		return b


import math

class Solution:

	def sieveOfEratosthenes(self, N):
		arr = [True] * (N + 1)
		lst = []
		sq = int(math.sqrt(N))
		for i in range(2, sq + 1):
			if arr[i]:
				for j in range(i + 1, N + 1):
					if j % i == 0:
						arr[j] = False
		arr[0] = False
		arr[1] = False
		for i in range(len(arr)):
			if arr[i] == True:
				lst += [i]
		return lst


import math as m

class Solution:

	def sieveOfEratosthenes(self, N):
		res = [True] * (N + 1)
		res[0] = res[1] = False
		for i in range(2, m.ceil(m.sqrt(N))):
			if res[i]:
				for j in range(i + i, len(res), i):
					res[j] = False
		a = [i for i in range(len(res)) if res[i]]
		return a


class Solution:

	def sieveOfEratosthenes(self, N):
		e = []
		sieve = [True] * (N + 1)
		sieve[0] = False
		sieve[1] = False
		s = int(N ** 0.5) + 1
		for i in range(2, s):
			if sieve[i]:
				for j in range(i + i, N + 1, i):
					sieve[j] = False
		for i in range(len(sieve)):
			if sieve[i] == True:
				e.append(i)
		return e


import math as math

class Solution:

	def sieveOfEratosthenes(self, n):
		ans = []
		sieve = [True] * (n + 1)
		sieve[0] = False
		sieve[1] = False
		l = int(math.sqrt(n))
		for i in range(2, l + 1):
			if sieve[i]:
				for j in range(i + i, n + 1, i):
					sieve[j] = False
		for k in range(len(sieve)):
			if sieve[k] == True:
				ans.append(k)
		return ans


import math

class Solution:

	def sieveOfEratosthenes(self, N):
		l = ['T'] * (N + 1)
		m = []
		l[1] = 'f'
		l[0] = 'f'
		for i in range(2, int(math.sqrt(N)) + 1):
			for j in range(i + i, N + 1, i):
				if j % i == 0:
					l[j] = 'F'
		for i in range(2, N + 1):
			if l[i] == 'T':
				m.append(i)
		return m


import math

class Solution:

	def sieveOfEratosthenes(self, n):
		a = []
		l = ['f', 'f']
		l = l + ['t'] * (n - 1)

		def p(k):
			c = 0
			for r in range(2, int(math.sqrt(k) + 1)):
				if k % r == 0:
					return 0
			else:
				return 1
		for i in range(2, int(math.sqrt(n) + 1)):
			if p(i):
				for j in range(i + 1, n + 1):
					if j % i == 0:
						l[j] = 'f'
			else:
				l[i] = 'f'
		for i in range(len(l)):
			if l[i] == 't':
				a.append(i)
		return a


class Solution:

	def sieveOfEratosthenes(self, N):
		l = [True for i in range(N + 1)]
		s = int(N ** 0.5)
		l[0] = False
		l[1] = False
		for i in range(2, s + 1):
			for j in range(i + i, N + 1, i):
				if l[j] == True:
					l[j] = False
		l1 = []
		for k in range(N + 1):
			if l[k] == True:
				l1.append(k)
		return l1


class Solution:

	def sieveOfEratosthenes(self, N):

		def isprime(n):
			if n < 2:
				return 0
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return 0
			return 1
		c = []
		for i in range(2, N + 1):
			if isprime(i):
				c.append(i)
		return c


class Solution:

	def sieveOfEratosthenes(self, N):

		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
		d = []
		for i in range(2, N + 1):
			if prime(i):
				d.append(i)
		return d


import math

class Solution:

	def sieveOfEratosthenes(self, N):

		def isprime(N):
			if N == 0 or N == 1:
				return 0
			else:
				for i in range(2, int(math.sqrt(N)) + 1):
					if N % i == 0:
						return 0
				return 1
		l = []
		for i in range(2, N + 1):
			if isprime(i):
				l.append(i)
		return l


import math

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

class Solution:

	def sieveOfEratosthenes(self, N):
		a = []
		for i in range(2, N + 1):
			if isprime(i):
				a.append(i)
		return a


class Solution:

	def sieveOfEratosthenes(self, N):
		arr = [1] * (N + 1)
		arr[0] = 0
		arr[1] = 0
		no = 2
		while no * no <= N:
			if arr[no] == 1:
				for i in range(no * no, N + 1, no):
					arr[i] = 0
			no += 1
		lst = []
		for j in range(0, N + 1):
			if arr[j] == 1:
				lst.append(j)
		return lst


class Solution:

	def sieveOfEratosthenes(self, N):
		if N == 0 or N == 1:
			return 0
		l = []
		for i in range(N + 1):
			l.append(i)
		l[0] = 0
		l[1] = 0
		p = 2
		while p * p <= N + 1:
			if l[p] != 0:
				for i in range(p * p, N + 1, p):
					l[i] = 0
			p += 1
		res = []
		for i in l:
			if i:
				res.append(i)
		return res