Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Sieve of Euler

By: a guest on Feb 27th, 2011  |  syntax: C++  |  size: 2.46 KB  |  views: 82  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }
clone this paste RAW Paste Data