What is the order analysis of the following (using a list of primes)

Question

I have the following program:

Iterate x from 1 to N. Check to see if x is prime. If it is, add it to a list of primes.

The way I check to see if it is prime is iterating through the current list of primes, and seeing if they can divide x evenly.

What is the order analysis of this program? I don't think it is O(n^2), because the growing list of primes certainly doesn't increase at the rate of n. I don't it is O(nlog(n)), either.

How would I perform order analysis of the function?

Answer 1

You are using the naive methods of Primality testing. For a given n the number of primes < n is given by the prime counting function, which is approximately n/log(n). I'm not 100% sure of the complexity of this method as you generally will not need to divide by all primes < sqrt(n).

The slightly more sophisticated Sieve_of_Eratosthenes has complexity O(n log log n).