#include <iostream> // Para std::cout e std::endl
#include <vector> // Para std::vector
#include <cmath> // Para sqrt e ceil

int main(int, char const *[])
{
    // Fixa o limite nos primos a encontrar.
    // Tarefa: peca o valor ao usuario, ao inves de usar um fixo.
    int const N = 100;

    // Inicializa vetor de candidatos com 2, 3, ..., N
    std::vector<int> candidatos(N-1);
    for (int i{2}; i <= N; ++i) {
        candidatos[i-2] = i;
    }

    // A constante cancelado vai ser usada para indicar
    // os numero que sabemos que nao sao primos.
    int const cancelado = -1;

    // Agoritmo de Eratostenes:
    // Percorre cada candidato em ordem, se nao cancelado,
    // entao e primo e deve-se cancelar seus multiplos.
    // Ignora cancelados.
    // Percorre apenas ate sqrt(N), pois um dos fatores
    // primos de um numero nao primo deve ser menor ou
    // igual a sua raiz quadrada.
    // Usa ceil para evitar erros numericos de aproximacao
    // para baixo.
    for (int i{2}; i < ceil(sqrt(N)); ++i) {
        if (candidatos[i-2] != cancelado) {
            for (int j{2 * i}; j <= N; j += i) {
                candidatos[j-2] = cancelado;
            }
        }
    }
    // Agora os numero nao cancelados sao todos primos.

    // Imprime os numeros primos.
    for (auto candidato: candidatos) {
        if (candidato != cancelado) {
            std::cout << candidato << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}