trjhtr

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';

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 $sqrtn$ 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 yes1;
constexpr mytype no0;

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 stride2 * 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 nn";
 return 1;
 
 int natoi(argv[1]);
 if (n < 0) 
 std::cout << "Error: the number must be positiven";
 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.

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;

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).

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);