The Sieve of Eratosthenes Explained

Abstract

            Prime numbers are very important to the functioning of society and have many applications in a plethora of knowledge fields. From the fields of cybersecurity to engineering, they have been used extensively. Due to their importance, methods to find these prime numbers are very valuable. One of the earliest attempts to find prime numbers in a list was devised by Eratosthenes in ancient Greece. It is called the Sieve of Eratosthenes and it is a marvel of early algorithms. It’s ability to accurately and efficiently identity prime numbers in a list make it a very useful tool in the hands of computer scientists. This algorithm was changed and optimized over the course of time and it has been become an integral part of computer science. To understand the algorithm, first, its history and creation should be explored.

Background

            Eratosthenes of Cyrene was born in Cryene, North Africa during the Hellenstic Period of Ancient Greece. He lived for 82 years from the years of 276 BCE to 194 BCE. Through his life, he has contributed to multiple fields of knowledge from mathematics, astronomy and geography. He is considered the father of geography by many in the academic sphere. He is most famous for calculating the Earth’s circumference using the shadows created by the sun. The estimation that he arrived at is approximately around 3% of the actual measured value. Coming back to the study of algorithms, the sieve of Eratosthenes was first created in 240 BCE. The original work hasn’t survived but, it first appeared in the book “Introduction of Arithmetic” written by Nicomachus. The book attributes this algorithm to be created by Eratosthenes almost 400 years prior and is the only surviving evidence about its creation.

Erathosthenes of Cyrene

            The sieve of Eratosthenes deals with the idea of finding prime numbers in any given list of numbers. Before diving into how the algorithm works, it’s important to understand what a prime number is and what makes a specific number, a prime number. First, let’s start with a definition on what is considered an odd or even number (also called parity). In simple terms, an even number is any number that is a multiple of 2. For example, [0,2,4,6,8,…] are examples of this. An odd number can be defined as multiple of 2 plus 1. For example, [1,3,5,7,…]. Using this logic, one equation for each type of number can be created. Below are these two equations where m is the result and n is an integer multiplied by 2.

            Now that logic behind odd and even numbers are clear, the focus can be shifted to understand what makes a number, a prime number. In simple terms, a prime number is a number that is greater than 1 and has factors of only 1 and itself. Therefore, the only way to create it is through multiplying the number by 1. An example of this is, the number 3. As shown below, the factors for this number are 1 and 3. It has no other factors that can create that number. A number that has more factors is considered a composite number. An example of this is, the number 4. The factors of 4 are 1,2, and 4. Since it can be created using the number 2, it is considered a composite number.

            Going back to the parity discussion, since all even numbers are multiples of 2, it can be said that all even numbers are composite numbers except for the number 0. However, since odd numbers are a combination of multiples of 2 plus 1, it can be said that all prime numbers are odd but, it does not say that, all odd number numbers are prime. A good example of an odd composite number is 9. The number 9 has the factors of 1,3, and 9. Since it has more than 2 factors, that makes this odd number, a compositive number. So now, the problem is finding which of these odd numbers are considered prime numbers. As shown before, it’s more difficult to find prime number in a list of number than it is to find odd and even numbers. This is where the sieve of Eratosthenes comes to solve that problem.

import java.util.*;

class hierholzer {

    // Initialize all variables needed
    private Hashtable<String, LinkedList> graph; // Hashtable to work as dictionary
    private Random rand = new Random(); // For random numbers
    private String startNode; // Starting node of the algorithm
    private String currentNode; // Current node that is being tested
    private LinkedList<String> current_path; // Holds the nodes for the current path that the algorithm takes
    private LinkedList<String> final_path; // Holds the nodes from current_path that don't have remaining edges
    private int counter; // Used to place values in the front of the current_path list

    // Initializes the hashtable and linked lists
    public hierholzer() {
        this.graph = new Hashtable<String, LinkedList>();
        this.current_path = new LinkedList<String>();
        this.final_path = new LinkedList<String>();
    }

    // Adds node to existing graph
    public void addNode(String nodeName) {
        // Checks if graph contains the nodes
        // If not, then a new node is created
        if (!this.graph.containsKey(nodeName)) {
            LinkedList<String> edge = new LinkedList<String>();
            this.graph.put(nodeName, edge);
        }
    }

    // Adds edge to two nodes, both nodes get their own edge since it is undirected
    public void addEdge(String Node1, String Node2) {
        // Creates editable linked lists for each node
        LinkedList node1List = this.graph.get(Node1);
        LinkedList node2List = this.graph.get(Node2);

        // Places the second node name in a linked list for first node name
        if (!Node1.contains(Node2)) {
            node1List.add(Node2);
            this.graph.put(Node1, node1List);
        }

        // Places the first node name in a linked list for second node name
        if (!Node2.contains(Node1)) {
            node2List.add(Node1);
            this.graph.put(Node2, node2List);
        }
    }

    // Removes node from graph when all the edges have been used
    // Moves the first element to the final_path list
    // The second element in current_path becomes the current and starting node
    private void removeNode(String nodeName) {
        this.current_path.removeFirst(); // Remove first element from list
        if(!this.current_path.isEmpty()) { // Checks if list is empty
            this.currentNode = this.current_path.get(0); // Makes current_path's first element the current node
            this.startNode = this.currentNode; // current and starting nodes are the same
            this.counter = 0; // resets counter so it can place elements in the beginning of the existing list
            this.final_path.add(nodeName); // The removed node is appended to the final_path list
        } else {
            this.final_path.add(final_path.getFirst()); // Executes when it's the last element in the final_path list
        }
    }

    // Removes edge of two nodes from both linked lists
    private void removeEdge(String Node1, String Node2) {
        // Creates editable linked lists for each node
        LinkedList node1List = this.graph.get(Node1);
        LinkedList node2List = this.graph.get(Node2);

        // Removes Node 2 from Node 1
        if(!Node1.contains(Node2)) {
            node1List.remove(Node2);
            this.graph.put(Node1, node1List);
        }

        // Removes Node 1 from Node 2
        if(!Node2.contains(Node1)) {
            node2List.remove(Node1);
            this.graph.put(Node2, node2List);
        }
    }

    private void pickStart() {
        String[] nodeList = this.graph.keySet().toArray(new String[0]); // Creates list of nodes
        int randIndex = rand.nextInt(nodeList.length); // Random node
        this.startNode = nodeList[randIndex]; // Selects random node
        this.currentNode = this.startNode; // Sets the start node also as current node
        this.current_path.add(this.startNode); // Adds node to current_path
    }

    // The main function that runs the Hierholzer's algorithm
    private void algorithm() {
        LinkedList nodeEdges = this.graph.get(currentNode); // Creates linked list of all the edges for the current node
        // Only works if the nodesEdges list is non-empty
        if(!nodeEdges.isEmpty()) {
            int randEdge = rand.nextInt(nodeEdges.size()); // Random edge
            String lastNode = this.currentNode; // Saves current node as last node
            this.currentNode = (String) nodeEdges.get(randEdge); // Using random edge, the current node is selected
            this.removeEdge(lastNode, this.currentNode); // Using last and current nodes, the edge is removed to show as completed
            this.counter++; // Iterates the counter to place in the front of current_path list
            this.current_path.add(counter, this.currentNode); // Appends, based on the counter, to the current_path list
            algorithm(); // Algorithm is run recursively until the all the edges for a node have been used
        } else { // Only works when the starting and current node are the same again
            if (!this.current_path.isEmpty()) { // Only works if the current path is non-empty
                removeNode(this.currentNode); // removes the Node from the current path since all edges are used
                algorithm(); // Algorithm is run again
            }
        }
    }

    // Runs the algorithm and posts the final Euler circuit path
    public void printCircuit() {
        pickStart(); // Picks the starting node
        System.out.println("The Euler Circuit of this graph is: (Starting Node: " + this.startNode + ")");
        this.algorithm(); // Runs the algorithm function
        // Prints the Euler path in a pleasing format
        for (int index = 0; index < this.final_path.size(); index++) {
            if (index == 0) {
                System.out.print(final_path.get(index));
            } else {
                System.out.print(" -> " + final_path.get(index));
            }
        }
    }
}