Confused as to why my algorithm is running slower than it should be

Question

Purely for fun, I decided to write a simple algorithm that finds all the prime numbers between 2 and x, where x is whatever you want it to be. I am using a clock_t to time how long it takes the algorithm to finish for varying x values. (I go x=0, then 25000, then 50000, then 75000, ..., up to 1,000,000). For example, when x = 25000, I go into a for loop with i going from 2 to 25000, and for each value of i, I check to see if it's prime by dividing it with every number between two and itself, looking for a remainder of 0.

Here is the algorithm:

vector<int> calcPrimesWithoutPrechecking(int upperLimit)
{
    vector<int> res;

    for(int i = 2; i <= upperLimit; i++)
    {
        int currentNum = i;
        bool foundDivisible = false;
        for(int j = 2; j < currentNum; j++)
        {
            if(currentNum % j == 0)
            {
                foundDivisible = true;
                break;
            }
        }

        if(!foundDivisible)
        {
            res.push_back(i);
        }
    }

    return res;
}

I figured I could make this faster by checking the last digit of the number we're currently testing. If that digit is a 0, 2, 4, 5, 6, or 8, then I don't have to even check if it's prime because I know it's not (of course 2, 3, and 5 are, so those are handled in the beginning). I'm calling this prechecking. Here is the algorithm with prechecking:

vector<int> calcPrimesWithPrechecking(int upperLimit)
{
    vector<int> res;
    res.push_back(2);res.push_back(3);res.push_back(5);    
    for(int i = 6; i <= upperLimit; i++)
    {
        bool foundDivisible = false;    
        int lastDig = i%10;
        if(lastDig == 0
            || lastDig == 2
            || lastDig == 4
            || lastDig == 6
            || lastDig == 8
            || lastDig == 5)
        {
            foundDivisible = true;
        }    

        int currentNum = i;
        for(int j = 2; j < currentNum && !foundDivisible; j++)
        {
            if(currentNum % j == 0)
            {
                foundDivisible = true;
                break;
            }
        }    

        if(!foundDivisible)
        {
            res.push_back(i);
        }
    }    
    return res;
}

I output the results to the console, as well as write them to a text file. I then copy the times over to excel, and plot them. However, for some reason the algorithm with prechecking is slower. I was almost sure it would be faster. When I run the program, I purposefully close every program on my computer and I run it in release mode. I have tested each algorithm in debug and they are indeed both working as intended.

Here is my data.

The x axis is the the number of primes we're checking (eg 25000 means we're looking for all primes between 2 and 25000), and the y axis is the time in seconds to get all the primes.

Can someone explain why the second algorithm, which should theoretically take out many of the computations, is in fact slower?

Answer 1

Because it doesn't take out many of the computations. If a number is even, that will be discovered immediately upon checking whether it is divisible by 2 (which is the first number you check in your loop). That's a lot faster than what you're doing here:

int lastDig = i%10;
if(lastDig == 0
    || lastDig == 2
    || lastDig == 4
    || lastDig == 6
    || lastDig == 8
    || lastDig == 5)

Answer 2

The reason the implementation with pre-checking is a little slower is that it needs to do more work to eliminate many of the numbers that would be eliminated after the first step of the inner loop anyway.

Consider number 8 as an example: pre-checking needs to find a division remainder and perform five comparisons before eliminating it, while the program with no pre-checking eliminates 8 too, but with a single division by two and a comparison to zero.

The only number for which you may see a little win is 5, but these are not nearly as common as even numbers, on which your program loses CPU cycles.

A better way to speed this one up is to avoid even numbers altogether: recall that all prime numbers after 3 are either of the form 6*k+1 or 6*k-1. Now you can iterate nearly three times as fast!

Another thing is that you do not need to check divisors past the square root of the candidate prime (can you prove why this is so?) This change alone will give you a huge improvement.

Finally, a very useful trick is to store all the primes that you have discovered so far, and use them for your trial divisors. This will greatly improve the speed of your inner loop.