|
Legendre Sieve
In mathematics, the Legendre sieve, named after Adrien-Marie Legendre, is the simplest method in modern sieve theory. It applies the concept of the Sieve of Eratosthenes to find upper or lower bounds on the number of primes within a given set of integers. Because it is a simple extension of Eratosthenes' idea, it is sometimes called the Legendre–Eratosthenes sieve.Iwaniec, HenrykThe sieve of Eratosthenes–Legendre Annali della Scuola Normale Superiore di Pisa – Classe di Scienze, Sér. 4, 4 no. 2 (1977), pp. 257–268 M453676!-- Bot generated title --> Legendre's identity The central idea of the method is expressed by the following identity, sometimes called the Legendre identity: :S(A,P)= \sum_\sum_ \mu(d) =\sum_\mu(d), A_d, , where ''A'' is a set of integers, ''P'' is a product of distinct primes, \mu is the Möbius function, and A_d is the set of integers in ''A'' divisible by ''d'', and ''S(A, P)'' is defined to be: :S(A, P) = , \, i.e. ''S''(''A'', ''P'') i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Adrien-Marie Legendre
Adrien-Marie Legendre (; ; 18 September 1752 – 9 January 1833) was a French mathematician who made numerous contributions to mathematics. Well-known and important concepts such as the Legendre polynomials and Legendre transformation are named after him. Life Adrien-Marie Legendre was born in Paris on 18 September 1752 to a wealthy family. He received his education at the Collège Mazarin in Paris, and defended his thesis in physics and mathematics in 1770. He taught at the École Militaire in Paris from 1775 to 1780 and at the École Normale from 1795. At the same time, he was associated with the Bureau des Longitudes. In 1782, the Berlin Academy awarded Legendre a prize for his treatise on projectiles in resistant media. This treatise also brought him to the attention of Lagrange. The ''Académie des sciences'' made Legendre an adjoint member in 1783 and an associate in 1785. In 1789, he was elected a Fellow of the Royal Society. He assisted with the Anglo-French Sur ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sieve Theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limit ''X''. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be. One successful approach is to approximate a specific sifted set of numbers (e.g. the set of prime numbers) by another, simpler set (e.g. the set of almost prime numbers), which is typically somewhat larger than the original set, and easier to analyze. More sophisticated sieves als ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sieve Of Eratosthenes
In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.Horsley, Rev. Samuel, F. R. S., "' or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers,''Philosophical Transactions'' (1683–1775), Vol. 62. (1772), pp. 327–347 This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime. Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes. The earliest known reference to the sieve ( grc, κόσκινον Ἐρατοσθένους, ''kóskinon Era ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Upper Bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an element of that is less than or equal to every element of . A set with an upper (respectively, lower) bound is said to be bounded from above or majorized (respectively bounded from below or minorized) by that bound. The terms bounded above (bounded below) are also used in the mathematical literature for sets that have upper (respectively lower) bounds. Examples For example, is a lower bound for the set (as a subset of the integers or of the real numbers, etc.), and so is . On the other hand, is not a lower bound for since it is not smaller than every element in . The set has as both an upper bound and a lower bound; all other numbers are either an upper bound or a lower bound for that . Every subset of the natural numbers has a lo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prime Number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, or , involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order. The property of being prime is called primality. A simple but slow method of checking the primality of a given number n, called trial division, tests whether n is a multiple of any integer between 2 and \sqrt. Faster algorithms include the Miller–Rabin primality test, which is fast but has a small chance of error, and the AKS primality test, which alway ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Eratosthenes
Eratosthenes of Cyrene (; grc-gre, Ἐρατοσθένης ; – ) was a Greek polymath: a mathematician, geographer, poet, astronomer, and music theorist. He was a man of learning, becoming the chief librarian at the Library of Alexandria. His work is comparable to what is now known as the study of geography, and he introduced some of the terminology still used today. He is best known for being the first person known to calculate the circumference of the Earth, which he did by using the extensive survey results he could access in his role at the Library; his calculation was remarkably accurate. He was also the first to calculate Earth's axial tilt, which has also proved to have remarkable accuracy. He created the first global projection of the world, incorporating parallels and meridians based on the available geographic knowledge of his era. Eratosthenes was the founder of scientific chronology; he used Egyptian and Persian records to estimate the dates of the ma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Möbius Function
The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted . Definition For any positive integer , define as the sum of the primitive th roots of unity. It has values in depending on the factorization of into prime factors: * if is a square-free positive integer with an even number of prime factors. * if is a square-free positive integer with an odd number of prime factors. * if has a squared prime factor. The Möbius function can alternatively be represented as : \mu(n) = \delta_ \lambda(n), where is the Kronecker delta, is the Liouville function, is the number ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Floor Function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or equal to , denoted or . For example, , , , and . Historically, the floor of has been–and still is–called the integral part or integer part of , often denoted (as well as a variety of other notations). Some authors may define the integral part as if is nonnegative, and otherwise: for example, and . The operation of truncation generalizes this to a specified number of digits: truncation to zero significant digits is the same as the integer part. For an integer, . Notation The ''integral part'' or ''integer part'' of a number ( in the original) was first defined in 1798 by Adrien-Marie Legendre in his proof of the Legendre's formula. Carl Friedrich Gauss introduced the square bracket notation in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Brun Sieve
In the field of number theory, the Brun sieve (also called Brun's pure sieve) is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Viggo Brun in 1915 and later generalized to the fundamental lemma of sieve theory by others. Description In terms of sieve theory the Brun sieve is of ''combinatorial type''; that is, it derives from a careful use of the inclusion–exclusion principle. Let A be a finite set of positive integers. Let P be some set of prime numbers. For each prime p in P, let A_p denote the set of elements of A that are divisible by p. This notation can be extended to other integers d that are products of distinct primes in P. In this case, define A_d to be the intersection of the sets A_p for the prime factors p of d. Finally, define A_1 to be A itself. Let z be an arbitrary positive real number. The object of the sieve is to estimate: S(A,P,z) = \b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Selberg Sieve
In number theory, the Selberg sieve is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Atle Selberg in the 1940s. Description In terms of sieve theory the Selberg sieve is of ''combinatorial type'': that is, derives from a careful use of the inclusion–exclusion principle. Selberg replaced the values of the Möbius function which arise in this by a system of weights which are then optimised to fit the given problem. The result gives an ''upper bound'' for the size of the sifted set. Let A be a set of positive integers \le x and let P be a set of primes. Let A_d denote the set of elements of A divisible by d when d is a product of distinct primes from P. Further let A_1 denote A itself. Let z be a positive real number and P(z) denote the product of the primes in P which are \le z. The object of the sieve is to estimate :S(A,P,z) = \left\vert A \setminus \bigc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Eratosthenes")
