I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Talk:Legendre prime counting function

From Rosetta Code

several questions[edit]

Several questions: In principle this function has infinite recursion, so it should have a cut-off for n smaller than some number. 2? Then it is not clear how primes are counted I presume 2 is the first prime, 3 the second prime etc. Perhaps this could be made clear in the intro. The case of '1' is also a bit strange (i see 0 and 1 in the results, probably because some ambiguity in how the question is now posed/explained).

I checked and indeed pi(1) should be 0 (fixed that). Yes, the first prime would be 2.--Wherrera (talk) 17:27, 5 August 2021 (UTC)

There are a few ways to exit the recursion:

One is to use the base case that pi(n) = 0 for n < 2.

Another method would be to keep a table of small primes (say primes <= 127) and count from the array when n is small.

the third method is to count from the sieved primes that you need to generate anyway, using a binary search, as the sieved primes could be large enough for binary search to be preferred.

In the examples, the CoffeeScript uses the identity pi(n) = 0 when n < 2. The Erlang version performs a binary search on the sieved primes (method 3.) --Davgot (talk) 19:07, 5 August 2021 (UTC)

Thanks for clarifying, and thanks for the update to the description, this makes it a lot more clear. Updated my Mathematica solution to have pi(1) = 0.