1

The Willan's formula is:

Willan's formula

So, is the normal simple way of finding nth prime better, or is this formula better? The mathematical funtions being used in it looked time-consuming. Would it be the better way if we were asked for the 1009th prime number?

FariyaAchhab
  • 43
  • 4
  • 5
    That formula is a mathematical novelty: it's not remotely practical for actual computation. Just about anything else you choose will be faster. – Mark Dickinson Sep 29 '22 at 15:52
  • A quick search leads to [this wikipedia article](https://en.wikipedia.org/wiki/Formula_for_primes#Formulas_based_on_Wilson's_theorem), which says that the *simpler* form of this formula is not efficient because it requires about `n-1` multiplications and modulo operations. I guess it could be faster than trial division, but probably not than any kind of sieve or other practical methods. – Nelfeal Sep 29 '22 at 15:53
  • @Nelfeal: Note that the simpler formula you're referring to doesn't produce the nth prime: it just has the properties that it only produces primes, and that it produces all primes. (It just gives you `n+1` if `n+1` is prime, and `2` otherwise.) – Mark Dickinson Sep 29 '22 at 15:57
  • @MarkDickinson Of course, but it can be used as a primility test to replace trial division. I'm not sure which one would be faster between O(n) multiplications and modulo operations and O(sqrt(n)) divisions (or rather quotient-remainder operations). – Nelfeal Sep 29 '22 at 16:02
  • [This](https://stackoverflow.com/a/69345662/2034787) – גלעד ברקן Sep 29 '22 at 16:05
  • To be clear: the full formula is definitely slower than trial division or any other "simple" way of finding the nth prime number, because it contains at least `2^n` factorials which could effectively be reduced to `2^n` multiplications, but that's still an exponential number of operations. Compared to trial division which is "only" O(n*sqrt(n)) operations. – Nelfeal Sep 29 '22 at 16:13
  • See also [this question](https://stackoverflow.com/q/73817595/238704), which has a couple of answers including one by me. – President James K. Polk Sep 29 '22 at 17:13
  • 2
    I would first use the Prime Number Theorem to estimate where the number is, then I'd back up slightly, and use https://en.wikipedia.org/wiki/Prime-counting_function to count primes. And then use a sieve to find the exact answer. – btilly Sep 29 '22 at 17:13

0 Answers0