Estimation of time required for calculation in Eratosthene's sieve algorithm

Question

I am using Qt and cpp to calculate some time consuming calculation like prime number calculation using Eratosthene's sieve algorithm as shown below.

 QElapsedTimer timer;
        timer.start();

        int p;
        for ( p = 2ull; p * p <= n; p++)
        {

            // If prime[p] is not changed,
            // then it is a prime

            qDebug() << p << "something inside  prime number calculation";
            emit progressBarUpdatePrime(p*p+2);

            if (prime[p] == true)
            {
                // Update all multiples
                // of p greater than or
                // equal to the square of it
                // numbers which are multiple
                // of p and are less than p^2
                // are already been marked.
                sync.lock();
                if(pausePrime)
                   pauseCond.wait(&sync); // in this place, your thread will stop to execute until someone calls resume
                sync.unlock();
                qDebug() << p << "is a prime number";
                MyThread2().msleep(1000);
                emit NumberChanged(p);
                for (int i = p * p; i <= n; i += p){
                    prime[i] = false;
                }
            }
        }
        emit NumberChanged(9999ull);
        if(p * p >= n){
             qDebug() << p << "p value here";
            emit progressBarUpdatePrime(n);
            emit elapsedTimePrime(timer.elapsed());
            emit estimatedTimePrime((n * log10(log10(n))) + 2);
        }

My question is how to calculate he estimated time for this calculation. I used n * log10(log10(n) but that counts for number of iterations.

Answer 1

Lets ignore if a number is prime or not. Estimating that is a big math problem involving the density of primes and such. Lets just assume every number is prime. That gives:

The code marks all even numbers, so that is N/2 operations. Then all numbers divisible by 3, so N/3 operations. Then N/4, N/5, N/6, N/7, ...

So overall it's the sum i = 2 to sqrt(N): N/i. There is probably a formula to compute or estimate this.

Now in the outer loop we can advance the progress by n / p. If p is prime then the algorithm actually does the work but we just count it as doing n / p work every time. So the progress bar will jump a bit for non primes. It will also speed up towards the end because the work for p isn't actually n / p but n / p - p. You could use that figure in the sum above but then I don't think there is a formula for it and you have to sum it up in a loop.

Note: update the progress after the work for p has been done at the end of the loop, not at the start.

---

As a side node some improvements for your algorithm:

1. start with emit NumberChanged(2);, we now 2 is a prime and all other even numbers are not. No need to have them in the sieve at all.

2. Half the size of the prime array (+ 1 iirc to avoid out of bounds) and change all prime[x] to prime[x / 2]

3. The outer loop becomes for ( p = 3ull; p * p <= n; p += 2). Only odd numbers are checked

4. The inner loop becomes for (int i = p * p; i <= n; i += 2 * p). Only odd multiples of p must be marked.

This improvement uses half the memory, skips the most expensive p=2 step and step 4 doubles the speed.