2013-08-13

There are approximately N/ln(N) primes between N and 2N

Just saw this very nice video by @numberphile, and thought I whip up a small Python program to demonstrate the prime number theorem:
#!/usr/bin/env python
#
# "Chebyshev said it, and I say it again: There's always a prime between n and 2n."
#

import sys
import math

class PrimeFinder:

    def __init__( self, n ):
        self.n = n
    
    def isNPrime( self, N ):
        for x in range( 2, int( math.sqrt( N ) ) + 1 ):
            if N % x == 0:
                return False
        return True

    def computeAllPrimesBetweenNAndTwoN( self ):
        result = []
        for N in range( self.n, 2 * self.n + 1 ):
            if self.isNPrime( N ):
                result = result + [ N ]
        return result

def main():
    if len( sys.argv ) != 2:
        print "Prints all prime numbers between N and 2N"
        print "Usage: %s N" % sys.argv[ 0 ]
        print "Where N is some positive, natural number."
        sys.exit( 0 )

    N = int( sys.argv[ 1 ] )
    primeFinder = PrimeFinder( N )
    allPrimes = primeFinder.computeAllPrimesBetweenNAndTwoN()
    print "There are %u primes between %u and %u: %s" % ( 
        len( allPrimes ), N, 2 * N, str( allPrimes )[ 1 : -1 ] 
    )

if __name__ == "__main__":
    main()
And it seems to work, but check WolframAlpha if you don't trust me :)
$ ./myprimes.py 100000
There are 8392 primes between 100000 and 200000: 100003, 100019, 100043 ...

No comments:

Post a Comment