Finding primes using the Sieve of Eratosthenes

Sieve of Eratosthenes.py

#!/usr/bin/env python3

def sieve_of_eratosthenes(n):
	'''
	Complexity : O(n log log n) + O(n) ~ O(n log log n)
	'''
	prime = [True for i in range(n+1)]
	p = 2

	# if there are no factors of n till sqrt(n) then the number is prime
	# factors of a number come in pairs
	# e.g. a x b = n (a >= sqrt(n) and b <= sqrt(n))
	
	while (p*p <= n):  				# while p <= sqrt(n)
		if prime[p]:  				# if the position is unmarked, only then check
			for x in range(p*2, n+1, p):  	# 2n, 3n, 4n, 5n ...
				prime[x] = False
		p += 1

	for x in range(2, n):
		if prime[x]:
			print(x, end=" ")

	print()

print("Printing primes from 2 to n")
num = int(input("Enter the value of n : "))

sieve_of_eratosthenes(num)