#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;
}