The sieve of Eratosthenes is an algorithm to find out all prim numbers of an integer given field.
1 | #ifndef eratosthenes_h
|
2 | #define eratosthenes_h
|
3 | #include "multiples.h"
|
4 | #include "deleteNode.h"
|
5 |
|
6 | struct node *eratosthenes(struct node **head_ref, int max) {
|
7 |     struct node *tmp = *head_ref;
|
8 |     int multiNum = 0;
|
9 |     int listNum = 0;
|
10 |     
|
11 |     while(tmp != NULL) {
|
12 |         
|
13 |         listNum = tmp->data;
|
14 |         
|
15 |         multiNum = multiples(listNum, listNum);
|
16 |         
|
17 |        deleteNode(head_ref, multiNum);
|
18 |         
|
19 |         while(multiNum < max) {
|
20 |             multiNum = multiples(listNum, multiNum);
|
21 |             deleteNode(head_ref, multiNum);
|
22 |         }
|
23 |         tmp = tmp->next;
|
24 |     }
|
25 |     return (*head_ref);
|
26 | }
|
27 |
|
28 | #endif |
1 | #ifndef addtolist_h
|
2 | #define addtolist_h
|
3 |
|
4 | void append(struct node **head_ref, int new_data) {
|
5 |     /* 1. allocate node */
|
6 |     struct node* new_node = new struct node;
|
7 |     struct node *last = *head_ref; /* used in step 5*/
|
8 |     
|
9 |     /* 2. put in the data */
|
10 |     new_node->data = new_data;
|
11 |     /*
|
12 |      3. This new node is going to be the last node, s
|
13 |      make next
|
14 |      of it as NULL
|
15 |     */
|
16 |     new_node->next = NULL;
|
17 |     
|
18 |     /*
|
19 |      4. If the Linked List is empty, then make the new node as head
|
20 |     */
|
21 |     if(*head_ref == NULL) {
|
22 |         new_node->prev = NULL;
|
23 |         *head_ref = new_node;
|
24 |         return;
|
25 |     }
|
26 |     
|
27 |     /* 5. Else traverse till the last node */
|
28 |     while(last->next != NULL)
|
29 |         last = last->next;
|
30 |     
|
31 |     /* 6. Change the next of last node */
|
32 |     last->next = new_node;
|
33 |     new_node->prev = last;
|
34 |     return;
|
35 | }
|
36 |
|
37 | void push(struct node **head_ref, int new_data) {
|
38 |     //allocate store for new node
|
39 |     struct node *new_node = new struct node;
|
40 |     
|
41 |     //put in data
|
42 |     new_node->data = new_data;
|
43 |     
|
44 |     //by first adding previous pointer is always NULL
|
45 |     new_node->prev = NULL;
|
46 |     
|
47 |     //link the old list off the new node
|
48 |     new_node->next = (*head_ref);
|
49 |     
|
50 |     //change pevious of head node to the new node
|
51 |     if((*head_ref) != NULL)
|
52 |         (*head_ref)->prev = new_node;
|
53 |     
|
54 |     //move the head to point to the new node
|
55 |     (*head_ref) = new_node;
|
56 | }
|
57 |
|
58 | #endif |
1 | #ifndef deletenode_h
|
2 | #define deletenode_h
|
3 | #include "search.h"
|
4 |
|
5 | struct node *deleteNode(struct node **head_ref, int wanted_data) {
|
6 |     struct node *wanted_node = search(head_ref, wanted_data);
|
7 |     
|
8 |     if(*head_ref == NULL || wanted_node == NULL)
|
9 |         return (*head_ref);
|
10 |     
|
11 |     if(*head_ref == wanted_node)
|
12 |         *head_ref = wanted_node->next;
|
13 |         
|
14 |     if(wanted_node->next != NULL)
|
15 |         wanted_node->next->prev = wanted_node->prev;
|
16 |         
|
17 |     if(wanted_node->prev != NULL)
|
18 |         wanted_node->prev->next = wanted_node->next;
|
19 |     
|
20 |     delete wanted_node;
|
21 |     
|
22 |     return (*head_ref);
|
23 | }
|
24 |
|
25 | #endif |
1 | #ifndef eratosthenes_h
|
2 | #define eratosthenes_h
|
3 | #include "multiples.h"
|
4 | #include "deleteNode.h"
|
5 |
|
6 | struct node *eratosthenes(struct node **head_ref, int max) {
|
7 |     struct node *tmp = *head_ref;
|
8 |     int multiNum = 0;
|
9 |     int listNum = 0;
|
10 |     
|
11 |     while(tmp != NULL) {
|
12 |         
|
13 |         listNum = tmp->data;
|
14 |         
|
15 |         multiNum = multiples(listNum, listNum);
|
16 |         
|
17 |        deleteNode(head_ref, multiNum);
|
18 |         
|
19 |         while(multiNum < max) {
|
20 |             multiNum = multiples(listNum, multiNum);
|
21 |             deleteNode(head_ref, multiNum);
|
22 |         }
|
23 |         tmp = tmp->next;
|
24 |     }
|
25 |     return (*head_ref);
|
26 | }
|
27 |
|
28 | #endif |
1 | #ifndef printlist_h
|
2 | #define printlist_h
|
3 | #include <iomanip>
|
4 | #include "numberOfDigits.h"
|
5 | using namespace std;
|
6 |
|
7 | void print_rightway(struct node *list) {
|
8 |     struct node *temp = list;
|
9 |     int counter = 1;
|
10 |     
|
11 |     cout << endl;
|
12 |     
|
13 |     while(temp != NULL) {
|
14 |         cout << temp->data << ", ";
|
15 |         counter++;
|
16 |         if(counter == 10) {
|
17 |             cout << endl;
|
18 |             counter = 0;
|
19 |         }
|
20 |         temp = temp->next;
|
21 |     }
|
22 |     cout << endl;
|
23 | }
|
24 |
|
25 | void print_reversed(struct node *list) {
|
26 |     struct node *temp = list;
|
27 |     int counter = 1;
|
28 |     
|
29 |     cout << endl;
|
30 |     
|
31 |     while(temp->next != NULL)
|
32 |         temp = temp->next;
|
33 |     while(temp != NULL) {
|
34 |         cout << temp->data << ", ";
|
35 |         counter++;
|
36 |         if(counter == 10) {
|
37 |             cout << endl;
|
38 |             counter = 0;
|
39 |         }
|
40 |         temp = temp->prev;
|
41 |     }
|
42 |     cout << endl;
|
43 | }
|
44 |
|
45 | void print_formated(struct node *list, int numbers) {
|
46 |     unsigned int number_of_digits = numberOfDigits(numbers);
|
47 |     
|
48 |     struct node *temp = list;
|
49 |     int counter = 0;
|
50 |     
|
51 |     cout << endl;
|
52 |     
|
53 |     while(temp != NULL) {
|
54 |         cout << setw(number_of_digits) << temp->data << ", ";
|
55 |         counter++;
|
56 |         if(counter == 10) {
|
57 |             cout << endl;
|
58 |             counter = 0;
|
59 |         }
|
60 |         temp = temp->next;
|
61 |     }
|
62 |     cout << endl;
|
63 | }
|
64 |
|
65 | #endif |
1 | #ifndef deletelist_h
|
2 | #define deletelist_h
|
3 |
|
4 | struct node *deleteList(struct node **head_ref) {
|
5 |     //reference to list for navigation
|
6 |     struct node *tmp_pointer = *head_ref;
|
7 |     
|
8 |     //walk through the list and erase
|
9 |     while(tmp_pointer != NULL) {
|
10 |         deleteNode(head_ref,tmp_pointer->data);
|
11 |         
|
12 |         tmp_pointer = tmp_pointer->next;
|
13 |     }
|
14 |     
|
15 |     return (*head_ref);
|
16 | }
|
17 |
|
18 | #endif |
1 | #include <iostream>
|
2 | #include "list.h"
|
3 | #include "addToList.h"
|
4 | #include "printList.h"
|
5 | #include "eratosthenes.h"
|
6 | #include "deleteList.h"
|
7 | using namespace std;
|
8 |
|
9 | int main(int argc, char **argv) {
|
10 |     struct node *newList = NULL;
|
11 |     int max = 2;
|
12 |     
|
13 |     cout << "Sieve of Eratosthenes" << endl;
|
14 |     cout << "Insert maximum (> 1): ";
|
15 |     cin >> max;
|
16 |     
|
17 |     for(int i = 2; i <= max; i++) {
|
18 |         append(&newList, i);
|
19 |     }
|
20 |     
|
21 |     cout << endl << "Field list:";
|
22 |     print_formated(newList,max);
|
23 |     eratosthenes(&newList, max);
|
24 |     cout << endl << "Prim numbers:";
|
25 |     print_formated(newList,max);
|
26 |     deleteList(&newList);
|
27 |     
|
28 |     delete newList;
|
29 |     
|
30 |     return 0;
|
31 | } |