#include <iostream>
#include <iomanip>
#include <vector>

std::vector<int> primos_ate(int limite);
void imprime_vetor(std::vector<int> const &v);

int main(int, char const *[]) {
  std::cout << "Calculo de primos ate um valor.\n";
  std::cout << "Forneca o valor maximo: ";

  int limite;
  std::cin >> limite;

  std::cout << "Primos ate " << limite << std::endl;

  std::vector<int> primos;

  primos = primos_ate(limite);

  imprime_vetor(primos);

  return 0;
}

std::vector<int> primos_ate(int limite) {
  int const cancelado = -1;
  std::vector<int> candidatos(limite + 1);
  for (int i = 0; i <= limite; ++i) {
    candidatos[i] = i;
  }

  int candidato_corrente = 2;
  while (candidato_corrente < limite + 1) {
    for (int i = 2 * candidato_corrente; i < limite + 1;
         i += candidato_corrente) {
      candidatos[i] = cancelado;
    }
    ++candidato_corrente;
    while (candidato_corrente < limite + 1 &&
           candidatos[candidato_corrente] == cancelado) {
      ++candidato_corrente;
    }
  }

  std::vector<int> primos;
  for (int i = 2; i < limite+1; ++i) {
      if (candidatos[i] != cancelado) {
          primos.push_back(i);
      }
  }

  return primos;
}

void imprime_vetor(std::vector<int> const &v) {
  for (auto x : v) {
    std::cout << std::setw(4) << x << " ";
  }
  std::cout << std::endl;
}