• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# Sieve of Euler

a guest Feb 27th, 2011 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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>();