Given a positive integer N, find the sum of all prime numbers between 1 and N(inclusive).
 
Example 1:
Input: N = 5
Output: 10
Explanation: 2, 3, and 5 are prime
numbers between 1 and 5(inclusive).
Example 2:
Input: N = 10
Output: 17
Explanation: 2, 3, 5 and 7 are prime
numbers between 1 and 10(inclusive).
 
Your Task:
You don't need to read or print anything. Your task is to complete the function prime_Sum() which takes N as input parameter and returns the sum of all primes between 1 and N(inclusive).
 
Expected Time Complexity: O(N*log(N))
Expected Space Complexity: O(N)
Constraints:
1 <= N <= 1000000

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

	def prime_Sum(self, n):

		# Code here

Solutions:
import math

class Solution:

	def prime_Sum(self, n):

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


import math

class Solution:

	def prime_Sum(self, n):

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


import math

class Solution:

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


class Solution:

	def prime_Sum(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
		s = 0
		for i in range(2, n + 1):
			if arr[i] == 1:
				s += i
		return s


class Solution:

	def prime_Sum(self, n):
		import math
		cou = 0
		N = n
		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)
				cou += i
		return cou


class Solution:

	def prime_Sum(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.getNextPrimeNo(p + 1, n)
		lst = filter(lambda x: x > 0, lst)
		return sum(lst)

	def getNextPrimeNo(self, c, n):
		if c == 2 or n == 2:
			return 2
		for i in range(c, n + 1):
			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 prime_Sum(self, N):
		sum = 0
		p = 2
		prime = [True for i in range(N + 1)]
		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:
				sum += i
		return sum


class Solution:

	def prime_Sum(self, n):
		N = 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 sum(ans)


import math

class Solution:

	def prime_Sum(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)
		add = sum(l1)
		return add


class Solution:

	def prime_Sum(self, n):

		def prime(i):
			c = 2
			while c * c <= i:
				if i % c == 0:
					return -1
				c += 1
			return 1
		s = 0
		for i in range(2, n + 1):
			if prime(i) == 1:
				s += i
		return s


class Solution:

	def prime_Sum(self, n):
		b = [True for i in range(n + 1)]
		for i in range(2, n // 2 + 1):
			if b[i]:
				j = 2 * i
				while j <= n:
					b[j] = False
					j += i
		s = 0
		for i in range(2, n + 1):
			if b[i]:
				s += i
		return s


class Solution:

	def prime_Sum(self, n):
		a = 1
		sum = 0
		while a <= n:
			for i in range(2, int(a ** 0.5) + 1):
				if a % i == 0:
					break
			else:
				sum += a
			a += 1
		return sum - 1


import math

class Solution:

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

	def prime_Sum(self, n):
		count = 0
		for i in range(2, n + 1):
			if Solution.isprime(i) == 1:
				count += i
		return count


class Solution:

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

	def prime_Sum(self, n):
		c = 0
		for i in range(2, n + 1):
			if Solution.prime(self, i) == True:
				c += i
		return c


import math

class Solution:

	def prime_Sum(self, n):

		def prime(x):
			if x <= 1:
				return False
			for i in range(2, int(math.sqrt(x)) + 1):
				if x % i == 0:
					return False
			else:
				return True
		sum = 0
		for j in range(2, n + 1):
			if prime(j) == True:
				sum = sum + j
		return sum


import math

def isPrime(N):
	max_divisor = math.floor(math.sqrt(N))
	if N == 1:
		return 0
	if N == 2:
		return 1
	if N > 2 and N % 2 == 0:
		return 0
	for i in range(3, max_divisor + 1, 2):
		if N % i == 0:
			return 0
	return 1

class Solution:

	def prime_Sum(self, n):
		arr = []
		for i in range(2, n + 1):
			if isPrime(i):
				arr.append(i)
		return sum(arr)


def isprime(n):
	import math as m
	if n % 2 == 0 and n > 2:
		return False
	elif n % 3 == 0 and n > 3:
		return False
	else:
		for i in range(5, 1 + int(m.sqrt(n))):
			if n % i == 0 or n % (i + 2) == 0:
				return False
			else:
				i = i + 6
		return True

class Solution:

	def prime_Sum(self, n):
		if n < 2:
			return 0
		else:
			sum = 0
			for i in range(2, n + 1):
				if isprime(i):
					sum += i
			return sum


class Solution:

	def prime_Sum(self, n):

		def pr(n):
			if n == 2:
				return True
			for i in range(2, int(n ** 0.5) + 1):
				if n % i == 0:
					return False
			else:
				return True
		c = 0
		if n == 0 or n == 1:
			return 0
		else:
			for i in range(2, n + 1):
				if pr(i) == True:
					c += i
		return c


import math

class Solution:

	def prime_Sum(self, n):
		ans = 0
		for i in range(2, n + 1):
			flag = 1
			for j in range(2, int(math.sqrt(i)) + 1):
				if i % j == 0:
					flag = 0
					break
			if flag:
				ans += i
		return ans


class Solution:

	def prime_Sum(self, n):
		primes = []
		for i in range(2, n + 1):
			for j in range(2, int(i ** 0.5) + 1):
				if i % j == 0:
					break
			else:
				primes.append(i)
		s = sum(primes)
		return s


class Solution:

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


class Solution:

	def prime_Sum(self, n):
		if n == 1:
			return 0
		sum = 0
		for i in range(2, n + 1):
			flag = 0
			for j in range(2, int(i ** (1 / 2)) + 1):
				if i % j == 0:
					flag = 1
					break
			if flag == 0:
				sum = sum + i
		return sum


import math

class Solution:

	def prime_Sum(self, n):
		if n < 2:
			return 0
		sum = 0
		for i in range(2, n + 1):
			isPrime = True
			for j in range(2, int(math.sqrt(i)) + 1):
				if i % j == 0:
					isPrime = False
					break
			if isPrime:
				sum += i
		return sum


class Solution:

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

	def prime_Sum(self, n):
		s = 0
		for i in range(2, n + 1):
			if self.isPrime(i):
				s += i
		return s


import math

class Solution:

	def prime_Sum(self, n):
		prime = [True] * (n + 1)
		prime[0] = prime[1] = False
		lim = int(math.sqrt(n)) + 1
		for i in range(2, lim):
			for j in range(i * i, n + 1, i):
				prime[j] = False
		s = 0
		for i in range(2, n + 1):
			if prime[i] == True:
				s += i
		return s


class Solution:

	def prime_Sum(self, n):
		prime = [True] * (n + 1)
		prime[0] = prime[1] = False
		lim = int(n ** 0.5) + 1
		for i in range(2, lim):
			for j in range(i * i, n + 1, i):
				prime[j] = False
		s = 0
		for i in range(2, n + 1):
			if prime[i] == True:
				s += i
		return s


from math import sqrt

class Solution:

	def isprime(n):
		flag = 0
		if n > 1:
			for k in range(2, int(sqrt(n)) + 1):
				if n % k == 0:
					flag = 1
					break
		if flag == 0:
			return True
		else:
			return False

	def prime_Sum(self, n):
		sum = 0
		if n == 1:
			return sum
		for i in range(2, n + 1):
			if Solution.isprime(i):
				sum += i
		return sum


class Solution:

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


import math

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

class Solution:

	def prime_Sum(self, n):
		s = 0
		for i in range(2, n + 1):
			if isprime(i):
				s += i
		return s


class Solution:

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

	def prime_Sum(self, n):
		x = Solution()
		z = 0
		for i in range(1, n + 1):
			if x.prime(i):
				z += i
		return z


class Solution:

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

	def prime_Sum(self, n):
		s = 0
		ob = Solution()
		for i in range(1, n + 1):
			if ob.isPrime(i):
				s += i
		return s


from math import floor, sqrt

class Solution:

	def prime_Sum(self, n):
		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 = sum((i for i in range(2, n + 1) if primes[i]))
		return ans


from math import *

class Solution:

	def Prime(self, n):
		x = int(sqrt(n))
		for i in range(2, x + 1):
			if n % i == 0:
				return False
		return True

	def prime_Sum(self, n):
		if n == 1:
			return 0
		s = 0
		for i in range(2, n + 1):
			if ob.Prime(i):
				s += i
		return s


class Solution:

	def prime_Sum(self, n):
		primes = [1] * (n + 1)
		primes[1] = 0
		primes[0] = 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 = 0
		for i in range(n + 1):
			if primes[i] == 1:
				op += i
		return op


class Solution:

	def prime_Sum(self, n):
		if n == 1:
			return 0
		arr = [2]
		su = 2
		for x in range(3, n + 1):
			found = False
			for _ in arr:
				if x % _ == 0:
					found = True
					break
				if _ ** 2 > x:
					break
			if not found:
				arr.append(x)
				su += x
		return su


class Solution:

	def prime_Sum(self, n):
		sum = 0
		for i in range(2, n + 1):
			if i == 2:
				sum += 2
			elif self.check(i):
				sum += i
			else:
				continue
		return sum

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


from math import *

class Solution:

	def prime_Sum(self, n):

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


class Solution:

	def prime_Sum(self, n):
		res = 0
		sieve = [True] * (n + 1)
		for p in range(2, n + 1):
			if sieve[p]:
				res += p
				for i in range(p * p, n + 1, p):
					sieve[i] = False
		return res


import math

class Solution:

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

	def prime_Sum(self, n):
		su = 0
		for i in range(2, n + 1):
			if self.isprime(i):
				su += i
		return su


class Solution:

	def prime_Sum(self, n):
		a = [True for _ in range(n + 1)]
		primes = []
		for i in range(2, n + 1):
			if a[i]:
				for j in range(i * i, n + 1, i):
					a[j] = False
		for i in range(2, n + 1):
			if a[i]:
				primes.append(i)
		return sum(primes)


def sieveCode(n):
	isPrime = [True] * (n + 1)
	isPrime[0] = False
	isPrime[1] = False
	for i in range(2, n + 1):
		if isPrime[i]:
			for j in range(i * i, n + 1, i):
				isPrime[j] = False
	total = sum((i for i in range(n + 1) if isPrime[i]))
	return total

class Solution:

	def prime_Sum(self, n):
		return sieveCode(n)


import math

class Solution:

	def isprime(self, x):
		if x == 2 or x == 3:
			return True
		if x % 2 == 0:
			return False
		for i in range(3, math.floor(math.sqrt(x)) + 1, 2):
			if x % i == 0:
				return False
		return True

	def prime_Sum(self, n):
		s = 0
		for i in range(2, n + 1):
			if self.isprime(i):
				s += i
		return s


class Solution:

	def prime_Sum(self, n):
		if n == 1:
			return 0
		elif n == 2:
			return 2
		else:
			c = 2
			for i in range(3, n + 1):
				f = 1
				m = int(i ** 0.5)
				for j in range(2, m + 1):
					if i % j == 0:
						f = 0
						break
				if f == 1:
					c = c + i
			return c


import math

class Solution:

	def prime_Sum(self, n):

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


class Solution:

	def prime_Sum(self, n):
		P = 10 ** 6 + 5
		isprime = [1] * P
		isprime[0] = 0
		isprime[1] = 0
		pre = [0] * P
		for i in range(2, P):
			for j in range(i * i, P, i):
				isprime[j] = 0
			if isprime[i]:
				pre[i] = pre[i - 1] + i
			else:
				pre[i] = pre[i - 1]
		return pre[n]


class Solution:

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


def checkPrime(n):
	if n == 1:
		return False
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True

class Solution:

	def prime_Sum(self, n):
		if n == 1:
			return 0
		answer = 0
		for i in range(2, n + 1):
			if checkPrime(i):
				answer += i
		return answer


class Solution:

	def pr(n):
		if n == 1 or n == 0:
			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(n ** 0.5) + 1, 6):
			if n % i == 0 or n % (i + 2) == 0:
				return False
		return True

	def prime_Sum(self, n):
		s = 0
		for i in range(n + 1):
			if Solution.pr(i):
				s += i
		return s


class Solution:

	def prime_Sum(self, n):
		if n == 1:
			return 0
		is_prime = [True] * (n + 1)
		i = 2
		while i * i <= n:
			if is_prime[i]:
				for idx in range(i * i, n + 1, i):
					is_prime[idx] = False
			i += 1
		sum = 0
		for j in range(2, n + 1):
			if is_prime[j]:
				sum += j
		return sum


from math import sqrt

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

class Solution:

	def prime_Sum(self, n):
		sum = 0
		for i in range(n + 1):
			if primenumber(i):
				sum += i
		return sum


class Solution:

	def sieveOfEratosthenes(self, N):
		l = [i for i in range(0, N + 1)]
		i = 2
		while i * i <= N:
			j = 2
			while i * j <= N:
				l[i * j] = 0
				j = j + 1
			i = i + 1
		return filter(lambda x: x != 0, l[2:])

	def prime_Sum(self, n):
		s = self.sieveOfEratosthenes(n)
		return sum(s)


class Solution:

	def prime_Sum(self, n: int) -> int:
		from math import sqrt
		from typing import List

		def siveOfEratosthenes(num: int) -> List[int]:
			primes = [True for _ in range(num + 1)]
			primes[0] = primes[1] = False
			for i in range(2, int(sqrt(num + 1)) + 1):
				if primes[i]:
					for x in range(i ** 2, num + 1, i):
						primes[x] = False
			return [i for i in range(num + 1) if primes[i]]
		prime_numbers = siveOfEratosthenes(n)
		result = 0
		for prime in prime_numbers:
			result += prime
		return result


import math

class Solution:

	def prime_Sum(self, n):
		sum = 0
		if n == 1:
			return 0
		for i in range(2, n + 1):
			a = int(math.sqrt(i))
			for j in range(2, a + 1):
				if i % j == 0:
					break
			else:
				sum += i
		return sum


import math

class Solution:

	def prime_Sum(self, n):

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


def isprime(x):
	for i in range(2, round(pow(x, 0.5)) + 1):
		if x % i == 0:
			return False
		else:
			continue
	return True

class Solution:

	def prime_Sum(self, n):
		s = 2
		if n == 1:
			return 0
		if n == 2:
			return 2
		for i in range(3, n + 1):
			if isprime(i):
				s = s + i
		return s


from math import sqrt

class Solution:

	def prime_Sum(self, n):
		sum = 0
		if n == 1:
			sum = 0
		elif n == 2:
			sum += 2
		else:
			sum = sum + 2
			for x in range(3, n + 1):
				half = int(sqrt(x)) + 1
				if all((x % y != 0 for y in range(2, half))):
					sum = sum + x
		return sum


from math import sqrt

class Solution:

	def prime_Sum(self, n):
		ans = []
		s = 0
		for i in range(1, n + 1):
			if self.checkprime(i):
				s += i
		return s

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


import math

class Solution:

	def prime_Sum(self, n):
		l = []
		l1 = []
		for i in range(1, n + 1):
			l.append(i)
		for i in l:
			if i != 1:
				for j in range(2, int(math.sqrt(i)) + 1):
					if i % j == 0 and i != j:
						break
				else:
					l1.append(i)
		return sum(l1)


import math

class Solution:

	def prime_Sum(self, n):
		if n == 1:
			x = 0
		elif n == 2:
			x = 2
		else:
			x = 5
			for i in range(4, n + 1):
				y = 0
				for j in range(2, int(math.sqrt(i)) + 1):
					if i % j == 0:
						y = 1
						break
				if y == 0:
					x += i
		return x


class Solution:

	def prime_Sum(self, n):
		import math

		def is_prime(N):
			if N == 1:
				return False
			if N == 2:
				return True
			flag = 1
			for i in range(2, round(math.sqrt(N)) + 1):
				if N % i == 0:
					flag = 0
					break
			if flag == 0:
				return False
			else:
				return True
		ans = 0
		for i in range(1, n + 1):
			if is_prime(i):
				ans = ans + i
		return ans


import math

class Solution:

	def prime_Sum(self, n):
		sum = 0
		for i in range(2, n + 1):
			if self.cekPrime(i):
				sum += i
		return sum

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


class Solution:

	def prime_Sum(self, n):
		arr = [True] * (n + 1)
		arr[0] = False
		arr[1] = False
		summ = 0
		for i in range(n + 1):
			if arr[i]:
				summ += i
				for j in range(i + i, n + 1, i):
					if j % i == 0:
						arr[j] = False
		return summ


import math

class Solution:

	def prime_Sum(self, n):

		def is_prime(num):
			for i in range(2, math.floor(math.sqrt(num)) + 1):
				if num % i == 0:
					return False
			return True
		ans = 0
		for num in range(2, n + 1):
			if is_prime(num):
				ans += num
		return ans


import math

class Solution:

	def prime_Sum(self, n):
		su = 0
		for i in range(2, n + 1):
			f = 0
			for j in range(2, int(math.sqrt(i)) + 1):
				if i % j == 0:
					f = 1
					break
			if f == 0:
				su += i
		return su


class Solution:

	def isSafe(self, m):
		for i in range(2, int(m ** (1 / 2)) + 1):
			if m % i == 0:
				return False
		return True

	def prime_Sum(self, n):
		if n < 2:
			return 0
		ans = [2]
		for i in range(3, n + 1, 2):
			if self.isSafe(i):
				ans.append(i)
		return sum(ans)