4
\$\begingroup\$

How can I improve and optimise this code?

#include <iostream>
#include <vector>

std::vector<bool> sieve_of_eratosthenes(int n)
{
    std::vector<bool> primes(n+1, true);
    primes[0] = false;
    primes[1] = false;

    for (int i = 2; i <= n; i++)
    {
        if (primes[i] == true)
        {
            for (int j = i * 2; j <= n; j += i)
            {
                primes[j] = false;
            }
        }
    }
    return primes;
}

int main()
{
    int n;
    std::cout << "Enter number :\n";
    std::cin >> n;
    std::vector<bool> result = sieve_of_eratosthenes(n);
    std::cout << "Prime numbers upto " << n << " is :\n";
    for (int i = 0 ; i < result.size(); i++)
    {
        if (result[i] == true)
        {
            std::cout << i << " ";
        }
    }
    std::cout << '\n';
}
\$\endgroup\$
2
\$\begingroup\$

I see a few things that may help you improve your program.

Be careful with signed versus unsigned

If a negative number is passed to the sieve_of_eratosthenes function, it's unlikely to produce useful results. For that reason, it would make sense to reject negative numbers when getting the value from the user and/or declare the function to accept only unsigned.

Consider the user

Rather than require an interactive session, it would be convenient to specify the number on the command line. Also, grammatically, it seems to me that it should say "Prime numbers up to n are:"

Reduce iterations

Other than 2, only odd numbers are possible primes. For that reason, I'd suggest changing the initialization to this:

std::vector<bool> primes(n+1);
primes[2] = true;
// all odd numbers are possible primes
for (unsigned i = 3; i <= n; i+=2) {
    primes[i] = true;
}

Note that primes(n+1) will initialize the entire vector to false, inverting the initialization of the original code.

One need only iterate up to \$\sqrt{n}\$ for the outer loop. Some thinking about that should reveal why this is so.

In a similar vein, we can start the inner loop with the value of i * i because any smaller multiple will already have been crossed out.

Test alternative representations for performance

It's frequently asserted that some other representation, such as std::vector<std::byte> or std::vector<char> will be faster than std::vector<bool>. Intuitively this makes some sense because std::vector<bool> has to do packing and unpacking of bits to access. However, this intuition isn't always correct because of cache effects. That is, it's often faster to do complex manipulations in cache than it is to do simple operations on memory areas not in the cache. We can guess at this, but the better method is to test it on your machine with your compiler. To simplify such testing, I used this code:

#include <iostream>
#include <vector>
#include <cmath>

#if 0
#include <cstddef>
using mytype = std::byte;
#else
using mytype = bool;
#endif
constexpr mytype yes{1};
constexpr mytype no{0};

std::vector<mytype> sieve_of_eratosthenes(unsigned n) {
    std::vector<mytype> primes(n+1);
    primes[2] = yes;
    // all odd numbers are possible primes
    for (unsigned i = 3; i <= n; i+=2) {
        primes[i] = yes;
    }
    // we only have to check up to the square root of the limit
    unsigned limit = std::sqrt(n);
    for (unsigned i = 3; i <= limit; i+=2) {
        if (primes[i] == yes) {
            const unsigned stride{2 * i};
            for (unsigned j = i * i; j <= n; j += stride) {
                primes[j] = no;
            }
        }
    }
    return primes;
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        std::cout << "Usage: primesUpTo n\n";
        return 1;
    }
    int n{atoi(argv[1])};
    if (n < 0) {
        std::cout << "Error: the number must be positive\n";
        return 2;
    }
    std::vector<mytype> result = sieve_of_eratosthenes(n);
    std::cout << "Prime numbers up to " << n << " are:\n";
    for (unsigned i = 0 ; i < result.size(); i++) {
        if (result[i] == yes) {
            std::cout << i << '\n';
        }
    }
    std::cout << '\n';
}

Using a bash script using time and R on my machine (a 64-bit Linux box, using gcc version 7.3.1) I get the following results, but remember that your results may differ and so I'd strongly encourage you to do your own testing. In each of the graphs, the red line is the version using std::byte and the green line is the version using std::bool. As you can see, in my testing std::bool almost always wins in both execution speed and memory size.
timing results byte vs bool memory results byte vs bool

\$\endgroup\$
5
\$\begingroup\$

Aside from the other optimizations, if you are using the sieve to check for primality of a number, you can optimize further, every prime after 2 is odd, therefore any even number that isn't 2 is not prime. This can easily be checked without the sieve. I would suggest that marking all the even numbers false is superfluous. So mark 2 as true and start the outer loop at 3 and increment by 2. As was mentioned, the inner loop can start at i*i, and since this will be an odd number you only need to mark every other multiple, therefore you can increment by i*2. Something like this:

std::vector<bool> sieve_of_eratosthenes(int n)
{
    std::vector<bool> primes(n+1, true);
    primes[0] = false;
    primes[1] = false;
    int limit = (int)sqrt(n) + 1;
    for (int i = 3; i < limit; i += 2)
    {
        if (primes[i])
        {
            int step = i * 2;
            for (int j = i * i; j <= n; j += step)
            {
                primes[j] = false;
            }
        }
    }
    return primes;
}
\$\endgroup\$
  • \$\begingroup\$ This will not produce correct answers because it incorrectly indicates all even numbers are prime. \$\endgroup\$ – Edward Apr 15 '18 at 11:27
  • \$\begingroup\$ Like my answer says, check even numbers without the sieve. Use it for only odd numbers.. \$\endgroup\$ – tinstaafl Apr 15 '18 at 11:29
  • \$\begingroup\$ But that leaves all of the even numbers (except 2) in the vector set incorrectly. \$\endgroup\$ – Edward Apr 15 '18 at 11:30
  • \$\begingroup\$ Yes but none of the even numbers are used, only the odd ones. \$\endgroup\$ – tinstaafl Apr 15 '18 at 11:32
3
\$\begingroup\$

With your j loop in sieve_of_eratosthenes you can start at i * i, since all the multiples of i with factors less than i will have already been removed. And you can stop the i loop when i * i > n (a condition you can check when you find a new prime, before the j loop).

\$\endgroup\$
3
\$\begingroup\$

Don’t use the weird vector<bool>. Using a vector of bytes will be faster, and using a bitset will give you the compactness if that was your intent.

Writing if (x==true) is silly.

Use uniform initialization:

std::vector<std::byte> primes { n+1, true };

edit: (vector has an init-list constructor in addition to other constructors. Touted as a feature when uniform init was promoted, it actually causes headscratching in code reviews exactly as I just fell into myself!)

use auto (almost everywhere):

auto result= sieve(n);
\$\endgroup\$
  • \$\begingroup\$ I have doubts that a std::bitset would be a sufficient data structure to implement a reasonably sized sieve of eratosthenes. Anyways, I'd agree going with the std::vector<std::byte>. \$\endgroup\$ – πάντα ῥεῖ Apr 14 '18 at 10:07
  • \$\begingroup\$ @πάνταῥεῖ std::bitset can be of any length. It maintains an array of native-sized words, though Plauger’s does seem to have optimization for small values of N. \$\endgroup\$ – JDługosz Apr 14 '18 at 10:46
  • \$\begingroup\$ May be you misunderstood me. A std::bitset can be build on top of a max long long value. A std::vector<std::bitset<64>> might help to improve over a std::vector<bool> while keeping the compactness in memory, you have to adapt your index calculations though. \$\endgroup\$ – πάντα ῥεῖ Apr 14 '18 at 10:50
  • 2
    \$\begingroup\$ I'd advocate measuring rather than guessing when it comes to performance questions. \$\endgroup\$ – Edward Apr 14 '18 at 15:16
  • 1
    \$\begingroup\$ @Edward, IIRC it will cause compilation error, as the second element requires conversion. I tried to compile it, but the error is too cryptic to understand :) \$\endgroup\$ – Incomputable Apr 14 '18 at 16:34

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.