Creating vector of primes using Sieve of Eratosthenes Please review my Sieve of Eratosthenes implementation.

std::vector&lt;int&gt; generate(const int&amp; n) {
    std::vector&lt;bool&gt; input(n+1, true);
    for (int i = 2; i * i&lt;= n; ++i) {
        for (int j = i; i*j &lt;= n    ; ++j) {
            input[i*j] = false;
        }
    }
    std::vector&lt;int&gt; primes{};
    for (auto i = 1; i &lt;= n; ++i) {
        if (input[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}


How can I improve and make this faster?
From Wikipedia, the Sieve of Eratosthenes algorithm is:


  To find all the prime numbers less than or equal to a given integer n
  by Eratosthenes' method:
  
  
  Create a list of consecutive integers from 2 through n: (2, 3, 4,
  ..., n).
  Initially, let p equal 2, the first prime number.
  Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p,
  4p, etc.; 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.
  


Your algorithm does not seem right really, notably it skips the step 4 which is essential for fast operation; and there are some non-C++ idioms too


Do not return the std::vector; instead pass it as a reference to the function.
Do not pass integers as const references.
If n &lt; 2, return empty vector.
The Eratosthenes sieve goes like: "for all values from 2 to sqrt(n) - if the number is a prime then mark all its multiples not prime. However all multiples less than i * i have been marked already composite by previous iterations.
Do not multiply the loop variables when a simple addition suffices.
As a simple optimization, the 2 is always in the primes as we skipped the "no values" already; thus we add it. Then we iterate only odd integers starting from 3. 


Thus we get

std::vector&lt;int&gt; generate(int n) {
    std::vector&lt;int&gt; result = std::vector&lt;int&gt;();
    if (n &lt; 2) {
        return result;
    }

    // initialize the vector
    std::vector&lt;bool&gt; input(n + 1, true);

    // calculate the upper limit as the square root of
    // of N. all composite numbers &lt;= N must have a 
    // factor &lt;= sqrt(N)
    int sqrtN = (int)sqrt(n);

    // iterate from 2 up to the square root of N
    for (int i = 2; i &lt;= sqrtN; i ++) {
        if (! input[i]) {
            // i is a proven composite number,
            // all its multiples have been 
            // marked not prime by all its prime factors by now.
            continue;
        }

        // as an optimization, all multiples *less* than 
        // the square of i are already marked, (they have 
        // another prime factor less than i), so we can start
        // from the square which is the smallest composite
        // not yet marked
        for (int j = i * i; j &lt;= n; j += i) {
            input[j] = false;
        }
    }

    // as n &gt;= 2, then add 2 here
    result.push_back(2);

    // and check only odd numbers here,
    // no other even number can be set
    for (int i = 3; i &lt;= n; i += 2) {
        if (input[i]) {
            result.push_back(i);
        }
    }

    return result;
}


Of course you do not need the second loop to just fill in the result vector; if the input[i] is true (the continue was not executed), the number is a prime and you can push_back it to the result vector there:

if (! input[i]) {
    // i is an already proven composite number,
    // all its multiples have been 
    // marked not prime by all its prime factors by now.
    continue;
}

// i is a prime
result.push_back(i);