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

Question

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)

Answer 1

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)$.