1
\$\begingroup\$

I've been on a Project Euler spree and I've been solving problems and as you might know, many of them require you to use prime numbers. I've been using the following code to generate and store primes in a vector, but was wondering if there is any non-obvious speed-ups that will make a large difference on the runtime of the generation.

// Generate the primes upto N using the Sieve of Eratosthenes.
template<typename T>
std::vector<T> generatePrimes(T n) {
    std::vector<T> result = std::vector<T>();
    if(n < 2) {
        return result;
    }
    std::vector<int> input(n + 1, 1);
    // Calculates the upper limit of the numbers to check.
    T sqrtN = (T)sqrt(n);
    // Iterate till the square root.
    for(T i = 2; i <= sqrtN; i++) {
        if(!input[i]) {
            continue;
        }
        // Multiples are marked false.
        for(T j = i * i; j <= n; j += i) {
            input[j] = 0;
        }
    }
    // Add to result vector.
    result.push_back(2);
    for(T i = 3; i <= n; i += 2) {
        if(input[i]) {
            result.push_back(i);
        }
    }
    return result;
}

And it is called like so:

vector<unsigned int> primes = generatePrimes<unsigned int>(10'000);

Is there any other way to speed this up? Before I had changed a line where I create the input vector to int from bool and it resulted in a nice 2.3x speed increase. See here for benchmark.

\$\endgroup\$
4
\$\begingroup\$

A few things to consider:

Is having the function generic really necessary? Why not just make the data type unsigned long long instead? This way you can do some bounds checking.

I would suggest using a bitset to hold the raw data would be more efficient than using 32 bits to represent each 1 or 0.

All primes are odd except for 2. If you add 2 to the result vector, you can start the outer loop at 3 and increment by 2.

Since the outer loop will only be odd numbers the start of the inner loop will also be odd. Therefore in order to keep hitting the odd number multiples you can increment by i*2.

You can shorten the second loop by adding to the vector every time you find a prime in the outer loop. This way the second loop can start where the outer loop finishes.

There is also another algorithm you can use that is more highly optimised for making a list of primes, mind you it's also more complicated( sorry I can't remember the name off hand)

\$\endgroup\$
5
  • \$\begingroup\$ Could you please explain the second to last paragraph a bit? Having a bit of trouble parsing what you are trying to say. \$\endgroup\$ – Rietty Sep 28 '19 at 12:12
  • \$\begingroup\$ Instead of starting the second loop at the beginning, use the outer loop to add all the primes up to sqrtN. The second loop starts at sqrtN + 1 \$\endgroup\$ – user33306 Sep 28 '19 at 12:31
  • \$\begingroup\$ The second loop as in the inner loop, or the second loop under the comment // Add to result vector? \$\endgroup\$ – Rietty Sep 28 '19 at 16:29
  • \$\begingroup\$ Also on the topic of std::bitset but iirc it was slower to use than using a vector of primes, I tried it with vector<bool> which is implemented using std::bitset iirc. Also starting the second loop at sqrt(n) + 1 has no guarantee that it will be an odd number to start with? \$\endgroup\$ – Rietty Sep 28 '19 at 16:39
  • \$\begingroup\$ @Rietty - Not the inner loop the second loop where the primes are added. You can use a simple one line algorithm to adjust the start to the next odd number(x += (x+1)%2). If x is even it will add 1 to make it odd, otherwise it will add 0 and leave it the same. \$\endgroup\$ – user33306 Sep 28 '19 at 18:55
0
\$\begingroup\$

You can make it go quite a bit faster by using wheel factorization to eliminate processing or storing multiples of small primes. As @tinstaaf said, you can easily eliminate the even numbers and deal with 2 as special case when you're almost done.

You can consider an odds-only sieve as the first level of wheel factorization. A mod 6 wheel eliminate multiple of 2 and 3, a mod 30 wheel eliminates multiples of 2, 3, and 5, and is a sweet spot. If you look at numbers starting with 7 and skip multiples of 2, 3, and 5, only 8 out of the next 30 can possibly be prime. Since there are 8 bits in a byte, one byte can represent 30 prime candidates so you can squeeze a lot of data about primes into a small bit array.

But prime wheels beyond odds-only are more complex. Wikipedia has a good introduction to the subject.

\$\endgroup\$
3
  • \$\begingroup\$ That implementation is a bit complicated to glean the basic concept of, but I'll look more into it. \$\endgroup\$ – Rietty Sep 28 '19 at 20:44
  • \$\begingroup\$ @Rietty you're right about the complexity of Kim's primesieve. Wikipedia has a better intoduction to wheel factorization. But if your totally obsessed with the subject like me at the moment, Kim Walish's doc on the algorithms is fantastic, in my opinion. \$\endgroup\$ – Greg Ames Oct 8 '19 at 13:32
  • \$\begingroup\$ @Rietty edited my answer above to provide the Wikipedia link. It's too late to change my comment :-/ I'm still very much a code review noob. \$\endgroup\$ – Greg Ames Oct 8 '19 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.