In cryptography we sometimes have to estimate \(pi(x)\), and which is the number of primes between 0 and \(x\).
Estimate number of primes |
Theory
One of the simplest methods of calculating π(x) is to generate them and count. The following code does a sieve derived from a method defined by the Greek mathematician Eratosthenes. With this we filtering out multiples of each prime:
# https://asecuritysite.com/encryption/nprime import sys from mpmath import * start = 0 end = 100 if (len(sys.argv)>1): start=int(sys.argv[1]) if (len(sys.argv)>2): end=int(sys.argv[2]) def sieve(n): """ Generate the primes less than or equal to n using the sieve of Eratosthenes. """ primes, sieve = [], [True] * (n + 1) for p in range(2, n + 1): if sieve[p]: primes.append(p) for i in range(p * p, n + 1, p): sieve[i] = False return primes def pi(x): """Calculates the number of primes less than or equal to x.""" return len(sieve(x)) print ("Range from",start,"to ",end) est= pi(end)-pi(start) print ("Estimation of primes:\t\t\t",est) print ("Possibility of finding prime (%):\t",est/float(end-start)*100) print ("\n----- Using Riemannr method to estimate") print ("Estimation is:\t",int(riemannr(end))) print ("\nRange\tEst number of primes") val=1 for x in range(1,31): val=val*10 print ("10^",x,"\t","{:,}".format(int(riemannr(val))))
One of the methods used is calculates the prime counting function π(x) using Schoenfeld’s inequality:
\(\pi(x) - \mathrm{li}(x)| < \frac{\sqrt x \log x}{8 \pi}\)
One method which can be used to estimate the number of prime numbers is the Riemann R function. This is a smooth approximation for π(x). The function is defined using the rapidly convergent Gram series:
\(R(x) = 1 + \sum_{k=1}^{\infty} \frac{\log^k x}{k k! \zeta(k+1)}\)
A sample run is:
Range from 0 to 1000000 Estimation of primes: 78498 Possibility of finding prime (%): 7.8498 ----- Using Riemannr method to estimate Estimation is: 78527 Range Est number of primes 10^ 1 4 10^ 2 25 10^ 3 168 10^ 4 1226 10^ 5 9587 10^ 6 78527 10^ 7 664667 10^ 8 5761551 10^ 9 50847455 10^ 10 455050683 10^ 11 4118052494 10^ 12 37607910542 10^ 13 346065531065 10^ 14 3204941731601 10^ 15 29844570495886 10^ 16 279238341360977 10^ 17 2623557157055978 10^ 18 24739954284239496 10^ 19 234057667300228928 10^ 20 2220819602556027136 10^ 21 21127269485932298240 10^ 22 201467286689188773888 10^ 23 1925320391607837261824 10^ 24 18435599767347541311488 10^ 25 176846309399141946490880 10^ 26 1699246750872419937812480 10^ 27 16352460426841662628560896 10^ 28 157589269275973244548022272 10^ 29 1520698109714271704874745856 10^ 30 14692398897720432138328735744