Advertisement
Guest User

Sieve of Euler

a guest
Feb 27th, 2011
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <list>
  3.  
  4. using namespace std;
  5.  
  6. list<int>* sieve_of_euler(int upper_bound);
  7. list<int>* range_list(int low, int high);
  8. list<int>* scale_list(list<int>* lst, int scalar);
  9. list<int>* filter_list(list<int>* lst, list<int>* mask);
  10.  
  11. int main() {
  12.     int upper_bound = 100000;
  13.     cout << "Enter the upper bound: ";
  14.     cin >> upper_bound;
  15.  
  16.     list<int>* primes = sieve_of_euler(upper_bound);
  17.     for (list<int>::iterator it = primes->begin(); it != primes->end(); it++) {
  18.     cout << (*it) << endl;
  19.     }
  20.     delete primes;
  21.  
  22.     return 0;
  23. }
  24.  
  25. // Returns a list of all the primes up to and including upper_bound.
  26. list<int>* sieve_of_euler(int upper_bound) {
  27.     list<int>* primes = new list<int>();
  28.     list<int>* working_list = range_list(2, upper_bound);
  29.     while (true) {
  30.     int front = working_list->front();
  31.     bool reached_square_root = front * front >= upper_bound;
  32.     if (reached_square_root) {
  33.         for (list<int>::iterator it = working_list->begin();
  34.          it != working_list->end();
  35.          it++) {
  36.         primes->push_back(*it);
  37.         }
  38.         delete working_list;
  39.         break;
  40.     }
  41.     else {
  42.         primes->push_back(front);
  43.         list<int>* scaled_by_front = scale_list(working_list, front);
  44.         list<int>* multiples_removed = filter_list(working_list, scaled_by_front);
  45.         delete scaled_by_front;
  46.         delete working_list;
  47.         working_list = multiples_removed;
  48.         working_list->pop_front();
  49.     }
  50.     }
  51.     return primes;
  52. }
  53.  
  54. list<int>* range_list(int low, int high) {
  55.     list<int>* result = new list<int>();
  56.     int value = low;
  57.     while (value <= high) {
  58.     result->push_back(value);
  59.     value++;
  60.     }
  61.     return result;
  62. }
  63.  
  64. list<int>* scale_list(list<int>* lst, int scalar) {
  65.     list<int>* result = new list<int>();
  66.     for (list<int>::iterator it = lst->begin(); it != lst->end(); it++) {
  67.     result->push_back(scalar * (*it));
  68.     }
  69.     return result;
  70. }
  71.  
  72. // Every element in the first list, but not the second is returned in
  73. // the new list.  Assumes the two input lists are sorted in ascending
  74. // order.
  75. list<int>* filter_list(list<int>* lst, list<int>* mask) {
  76.     list<int>* result = new list<int>();
  77.     list<int>::iterator mask_it = mask->begin();
  78.     for (list<int>::iterator main_it = lst->begin(); main_it != lst->end(); main_it++) {
  79.     int main_elem = *main_it;
  80.     int mask_elem = *mask_it;
  81.     if (main_elem < mask_elem) result->push_back(main_elem);
  82.     else if (main_elem == mask_elem) mask_it++;
  83.     }
  84.     return result;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement