Prime Number Checker

Question

This is my prime number checker in C++. I know that calculating the square root of a number can be very costly, so I don't do it unless the number is larger than 10k, where we would have to check 2450 extra values \$5k-\sqrt{10k}\over2\$.

void primeChecker(std::vector<int> &primes, int val)
{
    int max = val > 10000 ? sqrt(val) : val / 2;
    for (int i = 0; primes[i] <= max; i++)
    {
        if (val % primes[i] == 0)
        {
            return;
        }
    }
    primes.push_back(val);
    std::cout << val << std::endl;
}

Running it like this, it takes a few seconds to calculate the top 1,000,000 primes:

int main()
{
    std::vector<int> primes;
    primes.push_back(2);

    for (int i = 3; i < 1000000; i+=2)
    {
        primeChecker(primes, i);
    }

    return 0;
}

Am I breaking any coding standards, and are there any ways to improve this?

Answer 1

Instead of hard-coding 1000000000, use a constant:

const int maxPrimes = 1000000000;

Then, use it in the loop like this:

for (int i = 3; i < maxPrimes; i+=2)

This will make it clear what this value is.

Regarding the timing, you could use something from <ctime> or another suitable library to time certain code sections. For instance, you may time the loop in main() or just the one in primeChecker() for testing purposes. This may be OS-dependent, so I'll let you decide on this if you wish to try it.

Answer 2

I know that calculating the square root of a number can be very costly, so I don't do it unless the number is larger than 10k

int max = val > 10000 ? sqrt(val) : val / 2;

Did you do any profiling to find out if this was actually an issue? It makes the code less understandable and smells of premature optimization to me. At the very least, you should leave a comment explaining why you're doing this for the maintainer.

Like Jamal mentioned for 1000000000, you should give 10k a meaningful constant name as well. Actually, a meaningful constant name could potentially remove the need for the comment I suggested.

Otherwise it looks good to my untrained eye. If you're really looking to squeeze out all the performance you can though, you might want to look at implementing a sieve instead.

Answer 3

As janos mentioned, a prime number sieve can be used for a significant performance increase. I've attached a commented implementation that's been somewhat optimized for speed as a reference.

#include <vector>
#include <cmath>

// calculate primes up to a limit via a simple sieve
std::vector<unsigned int> calc_primes(unsigned int limit)
{
    // no primes < 2
    if (limit < 2)
        return std::vector<unsigned int>();

    // our initial list
    std::vector<unsigned int> primes = {2};

    // via wikipedia: x / ln(x) roughly approximates the prime counting
    // function pi(x) and the maximum of pi(x) / (x / ln(x)) is around 1.2,
    // so we reserve that much space for the primes to avoid memory reallocation
    primes.reserve(1.25 * limit / log(limit));
    // ^ this actually reduces run time for large limits by around 10% on
    // my machine

    // to find out which numbers are prime we keep a vector of booleans
    // for ODD numbers, since we know all even numbers are not prime.
    // note that we assume all numbers are prime initially and work by
    // marking which numbers are not
    std::vector<bool> is_prime(limit / 2 + 1, true);
    // ^ the fact that vector<bool> is specialized for space (i.e. uses
    // bitwise access) speeds up this function a significant amount, replacing
    // bool with int on my machine increases run time by ~250%

    // start at 3 and go up to the square root of the limit
    for (unsigned int i = 3; i * i <= limit; i += 2)
    {
        // check if a number is prime (remember to divide by two,
        // integer division truncates so the fact that i is odd doesn't matter)
        if (is_prime[i / 2])
        {
            // if i is prime, mark its odd multiples as NOT prime, starting
            // at i * i (e.g. for 5: we mark 25, 35, 45, ... )
            //
            // we leave out the even multiples since we know they are not prime,
            // and we start at i * i because numbers below that will
            // have been marked previously (e.g. for 5: 15 will have been marked
            // when the outer loop was at i = 3, so when i = 5, it doesn't need
            // to be marked again)
            for (unsigned int j = i; i * j <= limit; j += 2)
                is_prime[(i * j) / 2] = false;
        }
    }

    // after we've gone through and marked the multiples of all the numbers up
    // to the square root of limit, we do another pass and check which numbers
    // still have is_prime[] equal to true
    for (unsigned int i = 3; i <= limit; i += 2)
        if (is_prime[i / 2])
            primes.push_back(i);

    return primes;
}

Other notes: remember to compile with optimization enabled (-O3 for gcc and clang, /Ox for Visual Studio) if you want your program to be fast. Here are some comparisons of timings using g++ and the -O3 optimization flag for a limit of one million (average time was obtained via repeating each method 100 times):

primeChecker: 42.9 ms
primeChecker: 41.8 ms (always sqrt()) 
sieve: 2.3 ms

With simple functions like this sometimes you're limited to actually making changes in the code, recompiling, and benchmarking over and over, but for larger programs it's useful to know how to use profiling tools like gprof or similar.

Answer 4

Running it like this, it takes a few seconds to calculate the top 1,000,000 primes:

Uhm, no, that's not what it does. The program finds all the primes not greater than 1,000,000 (apparently there are 78497.

---

You nicely put spaces around operators consistently almost everywhere, except here:

for (int i = 3; i < 1000000; i+=2)

It would be better to put spaces around the += in i+=2 like this:

for (int i = 3; i < 1000000; i += 2)

---

Although your algorithm seems to be fast, be aware that you can achieve faster performance by using a sieve, such as the Sieve of Eratosthenes.

Answer 5

Calculating the square root every time will speed up your programme.

The profiling down below is made with Python but the speed gain should be evident in C++ too.

def prime_check_with_sqrt(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return False
    limit = int(n**0.5)+1
    for i in range(3,limit,2):
        if n % i == 0:
            return False
    return True

def prime_check_without_sqrt(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return False
    limit = n
    for i in range(3,limit,2):
        if n % i == 0:
            return False
    return True

import time

start = time.time()
p = [i for i in range(10000) if prime_check_with_sqrt(i)]
print("Time with sqrt is ",time.time()-start)

start = time.time()
p = [i for i in range(10000) if prime_check_without_sqrt(i)]
print("Time withOUT sqrt is ",time.time()-start)

Prints:

('Time with sqrt is ', 0.024765968322753906)
('Time withOUT sqrt is ', 0.5289759635925293)

Answer 6

One thing is primeChecker() is not only checking the prime, but also printing it. This could be moved into main(), or I could write another function to take care of that.

After profiling my code, these are the results I got:

With sqrt: 2
Without sqrt: 170

And:

With sqrt: 1
Without sqrt: 172
With both: 1