Mathematics is the study of numbers, quantity, space, pattern, structure, and change. Mathematics is used throughout the world as an essential tool in many fields, including natural science, engineering, medicine, and the social sciences. Applied mathematics, the branch of mathematics concerned with application of mathematical knowledge to other fields, inspires and makes use of new mathematical discoveries and sometimes leads to the development of entirely new mathematical disciplines, such as statistics and game theory. Mathematicians also engage in pure mathematics, or mathematics for its own sake, without having any application in mind. There is no clear line separating pure and applied mathematics, and practical applications for what began as pure mathematics are often discovered.
Informally speaking, a graph is a set of objects called points, nodes, or vertices connected by links called lines or edges. In a proper graph, which is by default undirected, a line from point A to point B is considered to be the same thing as a line from point B to point A. In a digraph, short for directed graph, the two directions are counted as being distinct arcs or directed edges. Typically, a graph is depicted in diagrammatic form as a set of dots (for the points, vertices, or nodes), joined by curves (for the lines or edges). Graphs have applications in both mathematics and computer science, and form the basic object of study in graph theory.
Applications of graph theory are generally concerned with labeled graphs and various specializations of these. Many problems of practical interest can be represented by graphs. The link structure of a website could be represented by a directed graph: the vertices are the web pages available at the website and a directed edge from page A to page B exists if and only if A contains a link to B. A graph structure can be extended by assigning a weight to each edge of the graph. Graphs with weights, or weighted graphs, are used to represent structures in which pairwise connections have some numerical values. For example if a graph represents a road network, the weights could represent the length of each road. A digraph with weighted edges in the context of graph theory is called a network. Networks have many uses in the practical side of graph theory, network analysis (for example, to model and analyze traffic networks).
The sieve of Eratosthenes is a simple algorithm for finding all prime numbers up to a specified maximum value. It works by identifying the prime numbers in increasing order while removing from consideration composite numbers that are multiples of each prime. This animation shows the process of finding all primes no greater than 120. The algorithm begins by identifying 2 as the first prime number and then crossing out every multiple of 2 up to 120. The next available number, 3, is the next prime number, so then every multiple of 3 is crossed out. (In this version of the algorithm, 6 is not crossed out again since it was just identified as a multiple of 2. The same optimization is used for all subsequent steps of the process: given a prime p, only multiples no less than p2 are considered for crossing out, since any lower multiples must already have been identified as multiples of smaller primes. Larger multiples that just happen to already be crossed out—like 12 when considering multiples of 3—are crossed out again, because checking for such duplicates would impose an unnecessary speed penalty on any real-world implementation of the algorithm.) The next remaining number, 5, is the next prime, so its multiples get crossed out (starting with 25); and so on. The process continues until no more composite numbers could possibly be left in the list (i.e., when the square of the next prime exceeds the specified maximum). The remaining numbers (here starting with 11) are all prime. Note that this procedure is easily extended to find primes in any given arithmetic progression. One of several prime number sieves, this ancient algorithm was attributed to the Greek mathematicianEratosthenes (d. c. 194 BCE) by Nicomachus in his first-century (CE) work Introduction to Arithmetic. Other more modern sieves include the sieve of Sundaram (1934) and the sieve of Atkin (2003). The main benefit of sieve methods is the avoidance of costly primality tests (or, conversely, divisibility tests). Their main drawback is their restriction to specific ranges of numbers, which makes this type of method inappropriate for applications requiring very large prime numbers, such as public-key cryptography.