2
$\begingroup$

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)
$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.