# What is the time complexity of this algorithm of finding all prime numbers?

I came up with this algorithm for finding all prime numbers from 1 to n. This algorithm could already exist, if it does I don't know what it is called.

primes = []

n = int(input("Enter number : "))

for j in range(2,n+1):
flag = True
for i in primes:
if i*i>j:
break
if j%i == 0:
flag = False
break
if flag:
primes.append(j)
print(primes)


The following complexity is not tight; however closeby:

The complexity of the algorithm is at least $$\Omega(n \sqrt{n}/\log^2 n)$$ and at most $$O(n \sqrt{n}/\log n)$$.

For any natural number $$x$$, the number of primes smaller than $$x$$ is given by prime-counting function $$\pi(x)$$. It is known that $$\pi(x) = \Theta(x/\log x)$$ (wiki and wolfram) for any natural number $$x$$. Therefore, for any number $$j$$, the algorithm is doing at most $$\pi(\sqrt{j})$$ computations to check if $$j$$ is prime or not.

Thus, an upper bound complexity of your algorithm is $$\, n \cdot \pi(\sqrt{n}) = O(n \sqrt{n}/\log n)$$.

Now, we compute the lower bound complexity. Suppose that $$j$$ is a prime number. Then, the algorithm is doing at least $$\pi(\sqrt{j})$$ computations to check if $$j$$ is prime or not. Therefore the algorithm has the running time at least $$\sum_{j: prime} \pi(\sqrt{j})$$.

Note that $$\pi(n) = \Theta(n/\log n)$$. In other words, there exists constants $$c_1$$ and $$c_2$$ such that $$c_2 (n/\log n) \leq \pi(n) \leq c_1 (n/\log n)$$ for every $$n \geq n_o$$ for some sufficiently large $$n_o$$. Now, it is not very difficult to see that there exits a constant $$c$$ such that there are $$\Omega(n/\log n)$$ prime numbers larger than $$n/c$$ for every $$n \geq n_o$$ for some sufficiently large $$n_o$$.

Thus, the complexity of the algorithm over all the prime numbers is $$\sum_{j: \text{ prime}} \pi(\sqrt{j}) \geq \sum_{j: \text{prime and } j > n/c} \pi(\sqrt{j}) \geq \Omega(n/\log n) \cdot \pi(\sqrt{n/c}) = \Omega(n \sqrt{n}/\log^2 n)$$.