In this range, the number of consecutive natural numbers present is (P2-P). If this value is α , then,
International Journal of Scientific & Engineering Research Volume 3, Issue 1, January-2012 1
ISSN 2229-5518
A Simple formula to predict the number of primes
Prithvijit Chakrabarty
‘P’ are known.
The formula is developed by considering a continuous section of the number line between P and P2. The length of this section is repeatedly divided by primes below P to obtain the number of primes in the region. The process is similar to the Sieve of Eratosthenes. However, instead of elimi- nating the multiples of primes below P, it eliminates the number of multiples of these primes. This reduces it to a simplifia ble algebraic expression that can easily be implemented using programs.
—————————— ——————————
NY number can be tested to be a prime by checking divi- siblity by primes below its square root. If we consider a
number P2, where is a known prime, then, division of P2
with primes numbers below must be performed to test its
primality. In other words, if P2 is composite, it is guaranteed to
be divisible by prime numbers below P.
Similarly, if there are composites between the num-
bers P and P2, then they must be divisible by primes below
their square root. As they are less than P2, their square root
will be less than P and they will be divisible by primes below
P. Thus, all composite numbers from P to P2 are guaranteed to
be divisble by primes below P.
your paper.
The process of finding multiples of primes mentioned above can be used to find the total number of multiples of all primes up to P in the range of P to P2. As all composite numbers in this range are multiples of these primes, we can obtain the number of composite numbers in this range.
In this range, the number of consecutive natural numbers present is (P2-P). If this value is α , then,
α
Number of multiples of 2= α − 2
α
(= 2 )
α
If we consider 'n' consecutive natural numbers, then, half of α− 2
them them w n
e odd and half will be even, i.e, n
is range,
Number of multiples of 3=
there will be
2 even and
n dd numbers, or
2 multiples 3
of 2. Similarly, there will be
3 multiples of 3 in this range.
α
However, some of these multiples will be divisible by 2 as well. Thus, to find numbers divisible only by 3 and a number
(= 6 )
From the previous step, α =
α
2 × 2
greater than 3, we must find the number
of multiples of 3 among the clu n−
multiples
(2 − 1)× α mber of multiples of 3 can also be represented as
(1)
of 2. In a range of n, numbe
n − n − n
be 2
such num-
2 × 3
bers. Similarly, there will be 2
6 multip3les of 5 that are
α− α − α
divisible only by numbers greater5than 5 and 5. In this manner, the number of multiples of any prime 'p' in a range of 'n' con
Number of multiples of 5= 2 6
5
α
secutive natural numbers can be found by subtracting the total
(= 15 )
However, from the previous step, α −
α
2 is
α
6 × 3
number of multiples of primes below 'p' from 'n' and dividing
it with 'p'.
(3− 1 )× α
ay write the number of multiples of 5 as
————————————————
Prithvijit Chakrabarty,
PH: +91-9535720462,+9180-41109365
6× 5 (2)
α− α − α − α
E-mail: prithvichakra@gmail.com
Number of multiples of 7=
4 × α
2 6 15
7
(= 105 )
IJSER © 2012
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 2
ISSN 2229-5518
α α
As (5− 1)× α is
α
15 × 5 , the number of multiples of 7 will
grams, the number of primes can be predicted quickly and
be 15× 7 (3)
α− α − α − α − 4 α
with great ease due to the simplicity of the formula.
Number of multiples of 11=
8 × α
2 6 15
11
105
(= α α α 4 α
The previous step show that α − 2 − 6 − 15 (7− 1)× 4× α
Hence, the number of multiples of 11 will be
(4)
105× 11
In this manner, the number of multiples of all the prime numbers less than P can be found.
Now, from the expressions (i), (ii), (iii), (iv) the general pattern the numbers follow can easily be deducted.
If we consider the series formed by these numbers, then, the ith
term will be as follo ( pi− 1− 1)× ni− 1× α
pi× d i− 1
where,
pi-1 is the (i-1)th prime number,
pi is the ith prime number
ni-1 is the numerator of the (i-1)th term,
di-1 is the denominator of the (i-1)th term.
The total number of composite numbers that will be present between P and P2 k − 1 ( p − 1)× n × α
i= 0
pi× d i− 1
where i varies from 0 to k such that P is the kth prime number. The only exception to this is the number of multiples of 2(as there is no (-1)th prime.)
As the number of composite numbers can be found, the remaining numbers in the range must be prime. Thus, the number of primes from P to P2 is:
k − 1 ( p
− 1)× n × α
α − (∑
i= 0
number P).
i− 1
i− 1
pi × d i− 1
)− 1
(excluding the prime
or, k − 1 ( p − 1)× c × α
α − ( )− 1
i= 0 pi
(5)
where ci-1 is the coefficient of α of the (i-1) th term.
The most important property of the result (equation (v)) is that the presence of a large number of prime numbers can be detected by knowing a small number of primes. For example, there are only 7 primes below 11. If we know only these 7 primes, we can detect the presence of 25 other primes that are present between 11 and 121. Similarly, by finding out just 3 more primes, we can find the number of primes between
19 and 324. Thus, the range of the formula increases by a great extent with every prime number found.
This algorithm efficiently finds the number of primes in a giv- en range. Though it does not predict the actual primes that will be present from P to P2, when implemented using pro-
IJSER © 2012