Extensible prime generator: Difference between revisions

 

There are closed formulas for generating primes. One of such formula is the following:

here [''x''] is the integral part of ''x'', {''x''} is the fractional part of ''x'', and ''C'' is a real constant (similar to [https://en.wikipedia.org/wiki/Mills%27_constant Mill's constant]). We can prove that there is a constant ''C'', such that p(''n'') is exactly the ''n''th prime number for any natural number ''n''. The first digits of ''c'' are ''c''=0.359344964622775339841352348439200241924659634...

Haskell have [https://hackage.haskell.org/package/exact-real-0.12.5.1/docs/Data-CReal.html a library of constructive real numbers], where real numbers can be of an arbitrary precision. We can define this constant ''C'' '''exactly''' and use the above formula to calculate the ''n''th prime. This is not the fastest method, but one of the coolest. And it is not as bad as you may think. It took about 0.3 seconds to calculate 10,000th prime using this formula.