Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement