Fast Algorithm to find number of primes between two numbers

19,235

Solution 1

Since you want to go as high as 1000! (factorial). You will not be able to get exact results with currently known methods on current technology.

The Prime Counting Function has only been evaluated exactly for a handful of values up to 10^24. So no way you'll be able to hit 1000!.


But since you mention than an approximation may be fine, you can use the Logarithmic Integral as an approximation to the Prime Counting Function.

This is based on the Prime Number Theorem which says that the Prime Counting Function is asymptotic to the Logarithmic Integral.

Solution 2

There is a fast, simple approximation to the number of primes below a given bound. If you do not need exact values, then a difference of two evaluations of this formula will get you close.

Solution 3

You can survey your options here: http://en.wikipedia.org/wiki/Prime_counting_function

This also looks helpful: http://mathworld.wolfram.com/PrimeCountingFunction.html

May I inquire why you need it up to 1000! ? Looks like no one has ever counted that many before. There are 1,925,320,391,606,803,968,923 primes from 1-10^23. 1000! = 10^120. I'm curious now.

Solution 4

The prime counting algorithm developed by Lagarias and others, quoted by others, runs very roughly in O (n^(2/3)). Since a sieve for the primes from k1 to k2 takes roughly O (max (sqrt (k2), k2 - k1), you'd check how far your lower and upper bounds are apart and either do a sieve or use the prime counting algorithm, whichever will be faster.

BTW. The prime counting algorithm can be tuned to count the primes from 1 to n for various values n that are reasonably close together quicker than counting them individually. (Basically, it chooses a number N, creates a sieve of size n / N, and looks up N^2 values in that sieve. The O (n^(2/3)) comes from the fact that for N = n^(1/3) both operations take N^(2/3) steps. That sieve can be reused for different n, but different values need to be looked up. So for k different values of n, you make N a bit smaller, increasing the cost of the sieve (once only) but reducing the cost of the lookup (k times)).

For n around 1000!, there's no chance. You can't even count the number of primes in [n, n] for values of that size if n has no small(ish) factors.

Solution 5

The fastest method that I know would be to eliminate all of the known non-primes (even numbers, all the numbers with divisers lower than the start number in the range, etc) as fast as you can, then iterate over the rest and use something like the Euclidean algorithm to determine if that number is a prime.

Share:
19,235

Related videos on Youtube

Hari
Author by

Hari

Updated on June 04, 2022

Comments

  • Hari
    Hari almost 2 years

    My problem reduces to finding the number of primes between two given numbers.I could have a range as big as 1 to (1000)! and hence I am need of some mathematical optimizations.

    Clearly the sieve method would be too slow in this case. Is there any mathematical optimization that can be applied - like for instance, taking a smaller subset of this large space and making inferences about the rest of the numbers.

    P.S: It definitely looks like I might have reached a dead end - but all that I am looking for are some optimizations that could possibly help solve this. And also, I am only looking for a single-threaded approach.

    EDIT: One approach I have been thinking and can solve a lot of large prime number related problems - is for someone to maintain a global table of primes and make it available for lookup. Folks at the PrimeGrid project can contribute usefully towards this.

    • gnasher729
      gnasher729
      If you choose an N small enough such that a list of all primes <= N can be stored on a hard drive, then it would be quicker to calculate all those primes on the fly rather than reading them from the hard drive.
  • bweaver
    bweaver about 12 years
    anything performed on 100! is too slow.
  • user448810
    user448810 about 12 years
    Actually, 81! = 5.8 * 10^120. The original number, 1000!, is 4 * 10^2567. And currently the largest known value of the prime counting function is PrimePi(10^24) = 18435599767349200867866, assuming the Riemann hypothesis.
  • bweaver
    bweaver about 12 years
    You're right; Trying to remember how I arrived at my erroneous calculation--but last night is fuzzy
  • Will Ness
    Will Ness over 9 years
    "use Euclidean algorithm" to calculate the GCD of a given number with what? All numbers below sqrt(1000!) (== 79.26*367.88**500 = 5.6469*10^1284 or something) ?