Prime Number Calculator

Prime numbers have been the subject of study since antiquity and are still an active area of research. Circa 300 BC, the Alexandrian mathematician Euclid proved that the number of primes is infinite. His proof by contradiction hinges on the fact that every number has a unique prime factorization. To understand Euclid's argument, suppose that the set of primes is finite: 2, 3, 5, 7,..., p_k. Now consider 1 plus the product of these k primes, the number

1 + 2⋅3⋅5⋅7⋅...⋅p_k

If this number is prime, then it contradicts the assertion that there are only k prime numbers. If this number is not prime, then it has some prime divisors and these prime divisors are not in the original set, thus contradicting the assumption that there are only k primes. Since the assumption of a finite number of primes leads to a contradiction, the set of prime numbers must be infinite.

Since Euclid's time, our understanding of prime numbers has grown. One of the most fundamental problems in the study of prime numbers involves the function π(x), the number of primes less than or equal to x.

In 1792, Gauss proposed (but did not prove) that π(x) ∼ x/ln(x), and later refined his conjecture to π(x) ∼ Li(x), where Li(x) is the logarithmic integral

Li(x) = ∫^x₂  dt/ln(t)

Gauss's conjecture became known as the Prime Number Theorem, which was independently proved in 1896 by Hadamard and de la Vallée Poussin.

Other Properties of Prime Numbers

Like the harmonic series of natural numbers, the harmonic series of primes is also divergent, that is,

Σ 1/p = ∞

where p ranges over all the prime numbers. If S(n) denotes the sum of the first n primes, then S(n) is approximated by the equation

S(n) ∼ (n²/2)[ln(n) + ln(ln(n)) - 1.5] ¹

For example,

S(6000) = 2 + 3 + 5 + 7 + ... + 59359 = 168448721, and

(6000²/2)[ln(6000) + ln(ln(6000)) - 1.5] = 168530075.93,

a difference of 0.0483%. A surprisingly simple inequality ² for the sum of the first n primes is given by

np_n > 2Σⁱ⁼ⁿ_i=1  p_i

where p_i is the i^th prime.

Primes and the Riemann Zeta Function

The Riemann Zeta function, defined by

ζ(s) = Σ^∞_n=1  1/n^s

has a surprising number of connections to the prime numbers. For example, the Euler Product Formula states that

ζ(s) = Π p^s/(1 - p^s)

where p ranges over all the primes. This relation is equivalent to

1/ζ(s) = Π (p^s - 1)/p^s

© Had2Know 2010