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.
sqrt()
entirely:for(int i=1,sqrti=1; i<N; i++) { if(sqrti*sqrti < i) sqrti++; ... }
\$\endgroup\$primeChecker()
inline and also passi
by reference. \$\endgroup\$