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