// sieve.cpp (Eratosthenes' Sieve)

#include <iostream>
#include <vector>


void write_number(int n)
{
    std::cout << " " << n;
}


void sieve(int n)
{
    std::vector<bool> is_prime(n + 1, true);  // Initializes variables

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            write_number(i);
            for (int j = i; j <= n / i; ++j) {
                is_prime[i * j] = false;
            }
        }
    }
}


int get_input()
{
    int n;
    std::cout << "This program lists all primes up to a given integer.\n"
              << "Enter an integer: ";
    std::cin >> n;
    return n;
}


int main()
{
    int n = get_input();
    if (n < 2) {
        std::cout << "There are no primes less than 2.\n";
    }
    else {
        std::cout << "The primes up to " << n << " are:";
        sieve(n);
        std::cout << ".\n";
    }
}