#include "sieve.h"
#include <cmath>

namespace
{
bool is_prime(int n)
{
    if (n % 2 == 0) {
        return false;
    }
    const int max_factor = static_cast<int>(std::sqrt(n));
    for (int probe = 2; probe <= max_factor; ++probe) {
        if (n % probe == 0) {
            return false;
        }
    }
    return true;
}
}

namespace sieve
{

std::vector<int> primes(int n)
{
    std::vector<int> result;
    if (n >= 2) {
        result.push_back(2);
    }
    for (int candidate = 3; candidate < n; ++candidate) {
        if (is_prime(candidate)) {
            result.push_back(candidate);
        }
    }
    return result;
}

}

#include "sieve.h"
#include <algorithm>
#include <list>
#include <numeric>

namespace sieve
{

std::vector<int> primes(int n)
{
    std::vector<int> result;
    std::list<int> candidates(n-1);
    std::iota(candidates.begin(), candidates.end(), 2);
    while (!candidates.empty()) {
        const int next = candidates.front();
        candidates.pop_front();
        result.push_back(next);
        candidates.remove_if([next](int n) { return n % next == 0; });
    }
    return result;
}

}

Implement the algorithm as described in the problem
Implement the algorithm as described in the problem
