prime number theorem


Also found in: Acronyms, Wikipedia.

prime number theorem

[¦prīm ¦nəm·bər ‚thir·əm]
(mathematics)
The theorem that the limit of the quantity [π(x)] (ln x)/ x as x approaches infinity is 1, where π(x) is the number of prime numbers not greater than x and ln x is the natural logarithm of x.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.

prime number theorem

(mathematics)
The number of prime numbers less than x is about x/log(x). Here "is about" means that the ratio of the two things tends to 1 as x tends to infinity. This was first conjectured by Gauss in the early 19th century, and was proved (independently) by Hadamard and de la Vall'ee Poussin in 1896. Their proofs relied on complex analysis, but Erd?s and Selberg later found an "elementary" proof.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
ERD6S, On anew method in elementary number theory which leads to an elementary proof of the prime number theorem, Proc.
Tabular values show that the predictions made using the chaotic dynamics approach are much closer to the actual primes than the predictions using the Prime Number Theorem.
The last, and longest, chapter introduces the basic concepts of algebraic graph theory, the prime number theorem for graphs, and the spectral properties of integral circulant graphs.
Emphasizing how complex analysis is a natural outgrowth of multivariable real calculus, this graduate textbook introduces the Cauchy integral formula, the properties and behavior of holomorphic functions, harmonic functions, analytic continuation, topology, Mergelyan's theorem, Hilbert spaces, and the prime number theorem. The third edition clarifies many of the later proofs.
In the case of the prime number theorem, Gauss later refined his conjecture but never did figure out how to prove it.
Thus the situation is quite different from the classical case on prime number theorem, where we have
Looking in turn at elementary methods, complex analysis methods, and probabilistic methods, he considers such topics as prime numbers, arithmetic functions, sieve methods, the method of van der Corput, the Euler gamma function, summation formulae, the prime number theorem and the Riemann hypothesis, two arithmetic application, primes in arithmetic progressions, densities, distributions of additive functions and mean values of multiplicative functions, and integers free of small prime factors.
Similar to the proof of the prime number theorem, with the help of Lemma 1, Lemma 2 and Perron's formula we get
On the other hand, by an explicit version of Prime Number Theorem in [8], we have estimates for [d.sub.n].
We note that for [alpha] = 0; relation (5) implies the "prime number theorem" ([3])
For any real number x > 1, from the Prime Number Theorem (see reference [6]) we know that there are at most O (x/ln x) primes in the interval [1, x], so from our Theorem we know that there are an infinity of numbers of the power k sieve sequence which are not prime.
So the percentage of primes is reducing significantly which is in accordance with prime number theorem, according to which, the probability that a random chosen number of size n is prime decreases as 1/d (where d is the number of digits of n).