C++, Visual Studios

Write a function that generates a vector of prime numbers between 2 and n. The function has 1 parameter, n, and returns a vector of integers. Use the Sieve of Eratosthenes to generate the vector of integers.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

Create a vector of consecutive integers from 2 through n: (2, 3, 4, ..., n).

Initially, let p equal 2, the smallest prime number.

Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).

Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

Copy the unmarked numbers to the vector that the function returns.

The main idea here is that every value given to p will be prime, because if it were composite it would be marked as a multiple of some other, smaller prime. Note that some of the numbers may be marked more than once (e.g., 15 will be marked both for 3 and 5).

As a refinement, it is sufficient to mark the numbers in step 3 starting from p2, as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate in step 4 when p2 is greater than n.[1] (Links to an external site.)Links to an external site.

Another refinement is to initially list odd numbers only, (3, 5, ..., n), and count in increments of 2p from p2 in step 3, thus marking only odd multiples of p. This actually appears in the original algorithm.[1] (Links to an external site.)Links to an external site. This can be generalized with wheel factorization (Links to an external site.)Links to an external site., forming the initial list only from numbers coprime (Links to an external site.)Links to an external site. with the first few primes and not just from odds (i.e., numbers coprime with 2), and counting in the correspondingly adjusted increments so that only such multiples of p are generated that are coprime with those small primes, in the first place.[6] (Links to an external site.)