Cannot understand this prime generator algorithm in my textbook

Question 1

Algorithm

The algorithm used by your prime generator code is called "Sieve of Eratosthenes". In general, it creates a list of numbers, and iterates over the list. All multiplications of the current number are removed from the list, and the remaining numbers are prime.

For example, let us consider [2,3,4,5,6,7,8,9,10,11,12,13,14,15]. We encounter 2, so we remove all even numbers from the list:

[2,3,5,7,9,11,13,15]

Same for 3:

[2,3,5,7,11,13]

5, 7, 11 and 13 have no multiplications in the list, so we remove nothing and remain with a list of primes.

Visual example

enter image description here

In this example (courtesy of Wikipedia), all multiplications of 2, 3 and 5 were removed from the list - multiplications of 2 were painted pink, multiplication of 3 were painted in green, and multiplications of 5 in dark blue. 7 will be iterated next, so it's highlighted. The dark colored numbers are prime, the light colored numbers are not prime, and the gray numbers have net yet been reached.

Optimizations in your code

As mentioned by @BenJackson, your code is optimized twice:

Firstly, it only stores odd numbers only starting from 3, because we know that even numbers are not prime (except 2).
Secondly, for the number p, it only starts to sieve from p². This is correct because if n<p then n*p was already sieved when multiplications of n were sieved.

This is the reason why the cryptic comment:

// sieving from p^2, whose index is 2i^2 + 6i + 3

Suppose that our algorithm has reached the second item in the vector, therefore i=2. The number in question is 5, because the index i denotes the number 2i+3 (first optimization).

We should sieve all multiplications of 5 from 25 onwards. The index that represents 25 is 11, because 25=2*11+3. Following your printouts, it removes indices 11, 16, 21, 26, ..., which correspond to the numbers 25, 35, 45, 55, .. - all odd multiplications of 5 we'd like to remove.

You can read more about it at Wikipedia or Wolfram MathWorld, and there's a nice javascript on-line demonstration here.

Question 2

The table of primes only stores odd values starting at 3 (obviously even values cannot be prime). The relation is given in the line int p = (i << 1) + 3, or p = 2i + 3. Now solve that for i, getting i = (p - 3)/2. Now what i corresponds to p^2? Plug in (2i+3)^2 to that second formula and simplify. Now you have the i for p^2 in terms of the i for p.

Example: Let's say i=1, thus the entry is_prime[i] is a test of the prime p=2i+3, or p=5. So yes, it is prime. Now the seive (explained elsewhere) wants to start marking non-primes at 25. It needs to know what i corresponds to 25. Now you could simply compute p*p and then insert that into i=(p-3)/2 and get j=11. The code has skipped those intermediate steps (as I showed above) to compute j=2i^2+6i+3 and gotten j=11 directly.

Question 3

Lines like these:

vector<int> generate_primes_from_1_to_n(const int &n) {
    int size = floor(0.5 * (n - 3)) + 1;

...

for(long i = 0; i < size; ++i) {
   if(is_prime[i]) {
       int p = (i << 1) + 3;

are a 'hack' so that the potential prime numbers 3, 5, 7, etc can be iterated over by iterating 0, 1, 2, 3 in i and using p for the corresponding possible primes 3, 5, 7, 9, etc.

It's a basic prime sieve other than that.

Question 4

As others have noted, i maps array locations and p maps the numbers that those array locations represent, according to the formula p = 2 i + 1. It may be easier to think about if you keep i and p explicitly in the program:

function primes(n)
    m := floor((n-1)/2)
    sieve := makeArray(0..m-1, True)
    i := 0; p := 3; ps := [2]
    while p * p <= n
        if sieve[i]
            append p to ps
            j := (p*p - 3) / 2
            while j < m
                sieve[j] := False
                j := j + p
        i := i + 1; p := p + 2
    while i < m
        if sieve[i]
            append p to ps
        i := i + 1; p := p + 2
    return ps

The strange formula for j in the original code is formed by taking the formula for j shown above and rewriting in terms of i instead of p.

If you're interested in programming with prime numbers, I have an essay at my blog that, among other things, discusses this exact formula in some depth.