#include <iostream>
#include <list>

using namespace std;

list<int>* sieve_of_euler(int upper_bound);
list<int>* range_list(int low, int high);
list<int>* scale_list(list<int>* lst, int scalar);
list<int>* filter_list(list<int>* lst, list<int>* mask);

int main() {
    int upper_bound = 100000;
    cout << "Enter the upper bound: ";
    cin >> upper_bound;

    list<int>* primes = sieve_of_euler(upper_bound);
    for (list<int>::iterator it = primes->begin(); it != primes->end(); it++) {
	cout << (*it) << endl;
    }
    delete primes;

    return 0;
}

// Returns a list of all the primes up to and including upper_bound.
list<int>* sieve_of_euler(int upper_bound) {
    list<int>* primes = new list<int>();
    list<int>* working_list = range_list(2, upper_bound);
    while (true) {
	int front = working_list->front();
	bool reached_square_root = front * front >= upper_bound;
	if (reached_square_root) {
	    for (list<int>::iterator it = working_list->begin();
		 it != working_list->end();
		 it++) {
		primes->push_back(*it);
	    }
	    delete working_list;
	    break;
	}
	else {
	    primes->push_back(front);
	    list<int>* scaled_by_front = scale_list(working_list, front);
	    list<int>* multiples_removed = filter_list(working_list, scaled_by_front);
	    delete scaled_by_front;
	    delete working_list;
	    working_list = multiples_removed;
	    working_list->pop_front();
	}
    }
    return primes;
}

list<int>* range_list(int low, int high) {
    list<int>* result = new list<int>();
    int value = low;
    while (value <= high) {
	result->push_back(value);
	value++;
    }
    return result;
}

list<int>* scale_list(list<int>* lst, int scalar) {
    list<int>* result = new list<int>();
    for (list<int>::iterator it = lst->begin(); it != lst->end(); it++) {
	result->push_back(scalar * (*it));
    }
    return result;
}

// Every element in the first list, but not the second is returned in
// the new list.  Assumes the two input lists are sorted in ascending
// order.
list<int>* filter_list(list<int>* lst, list<int>* mask) {
    list<int>* result = new list<int>();
    list<int>::iterator mask_it = mask->begin();
    for (list<int>::iterator main_it = lst->begin(); main_it != lst->end(); main_it++) {
	int main_elem = *main_it;
	int mask_elem = *mask_it;
	if (main_elem < mask_elem) result->push_back(main_elem);
	else if (main_elem == mask_elem) mask_it++;
    }
    return result;
}