Skip to main content
9 of 9
Commonmark migration

Python 2, 67 65 62 bytes

f=lambda n,k=0,m=2,p=1:k/n or-~f(n,k+p%m*(`n`in`m`),m+1,p*m*m)

Test it on Ideone.

How it works

We use a corollary of Wilson's theorem:

corollary of Wilson's theorem

At all times, the variable p is equal to the square of the factorial of m - 1.

If k < n, k/n will yield 0 and f is called recursively. m is incremented, p is updated, and k is incremented if and only if m is a prime that contains n.

The latter is achieved by adding the result of p%m*(`n`in`m`) to k. By the corollary of Wilson's theorem if m is prime, p%m returns 1, and if not, it returns 0.

Once k reaches n, we found q, the nth prime that contains n.

We're in the next call during the check, so m = q + 1. k/n will return 1, and the bitwise operators -~ will increment that number once for every function call. Since it takes q - 1 calls to f to increment m from 2 to q + 1, the outmost call to f will return 1 + q - 1 = q, as intended.

Dennis
  • 210.6k
  • 41
  • 370
  • 825