Sieve Of Eratosthenes

The sieve of Eratosthenes is an algorithm to find out all prim numbers of an integer given field.

list.h
1#ifndef eratosthenes_h
2#define eratosthenes_h
3#include "multiples.h"
4#include "deleteNode.h"
5
6struct 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
addToList.h
1#ifndef addtolist_h
2#define addtolist_h
3
4void 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
37void 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
search.h
1#ifndef search_h
2#define search_h
3
4struct node *search(struct node **head_ref, int wanted_data) {
5    struct node *tmp_pointer = *head_ref;
6    struct node *wanted_node = NULL;
7    
8    while(tmp_pointer != NULL) {
9        if(tmp_pointer->data == wanted_data)
10            wanted_node = tmp_pointer;
11        tmp_pointer = tmp_pointer->next;
12    }
13    
14    return wanted_node;
15}
16
17#endif
deleteNode.h
1#ifndef deletenode_h
2#define deletenode_h
3#include "search.h"
4
5struct 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
multiples.h
1#ifndef multiples_h
2#define multiples_h
3
4int multiples(int first, int second) {
5    //std::cout << first * second << ", ";
6    return first + second;
7}
8
9#endif
eratosthenes.h
1#ifndef eratosthenes_h
2#define eratosthenes_h
3#include "multiples.h"
4#include "deleteNode.h"
5
6struct 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
numberOfDigits.h
1#ifndef numberofdigits_h
2#define numberofdigits_h
3
4unsigned int numberOfDigits(int num) {
5    unsigned int counter = 0;
6    
7    do {
8        ++counter;
9        num /= 10;
10    }
11    while(num);
12    
13    return counter;
14}
15
16#endif
printList.h
1#ifndef printlist_h
2#define printlist_h
3#include <iomanip>
4#include "numberOfDigits.h"
5using namespace std;
6
7void 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
25void 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
45void 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
deleteList.h
1#ifndef deletelist_h
2#define deletelist_h
3
4struct 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
main.cpp
1#include <iostream>
2#include "list.h"
3#include "addToList.h"
4#include "printList.h"
5#include "eratosthenes.h"
6#include "deleteList.h"
7using namespace std;
8
9int 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}