Regex (Perl / Java / PCRE), 32 bytes
((?=(\2?+x*?(?!(xx+)\3+$))xx)x)*
Try it online! - Perl
Try it online! - Java
Try it online! - PCRE
Takes its input in unary, as a string of x characters whose length represents the number. Returns its output as the length of the match.
# tail = N = input value; no anchor needed, as every value returns a match
# Count the number of primes <= N, from the largest to the smallest prime.
( # J = 0
(?=
# \2 starts at zero, and on each subsequent iteration, contains the difference
# N-P-(J-1) where P is the previously found prime, and J is the running total of
# our prime count.
(
\2?+ # Start from the previous value of \2, atomically so that it
# can't be backtracked and started again from zero if the
# following fails to match. This will make tail = P-1, where
# P is the previously found prime.
x*? # Advance as little as necessary to make the following match,
# and add this to \2, while subtracting it from tail.
(?!(xx+)\3+$) # Assert tail is not composite; note that this needs to be
# inside group \2 for it to work in PCRE1 and older versions of
# PCRE2, which atomicize groups that have nested backreferences
)
xx # Assert tail is prime by eliminating the false positives 0, 1
)
x # J += 1; tail -= 1
)* # Iterate zero or more times, until there are no more smaller primes
# Return J as our match
Regex (Pythonregex / Ruby), 41 39 bytes
((?=(?=(\3?))(\2x*?(?!(xx+)\4+$))xx)x)*
Try it online! - Python import regex
Try it online! - Ruby
This is a port of the Perl/Java/PCRE regex to flavors that have no support for nested backreferences. Python's built-in re module does not even support forward backreferences, so for Python this requires regex.
# tail = N = input value; no anchor needed, as every value returns a match
# Count the number of primes <= N, from the largest to the smallest prime.
( # J = 0
(?=
# \2 starts at zero, and on each subsequent iteration, contains the difference
# N-P-(J-1) where P is the previously found prime, and J is the running total of
# our prime count.
(?=(\3?)) # \2 = \3 (or 0 if \3 is unset), to make up for the lack of
# nested backreferences
(
\2 # Start from the previous value of \3 (as copied into \2).
# This will make tail = P-1, where P is the previously found
# prime.
x*? # Advance as little as necessary to make the following match,
# and add this to \3, while subtracting it from tail.
(?!(xx+)\4+$) # Assert tail is not composite; note that this needs to be
# inside group \3 for it to work in PCRE1 and older versions of
# PCRE2, which atomicize groups that have nested backreferences
)
xx # Assert tail is prime by eliminating the false positives 0, 1
)
x # J += 1; tail -= 1
)* # Iterate zero or more times, until there are no more smaller primes
# Return J as our match
Regex (.NET), 35 bytes
((?=((?>\2?)x*?(?!(xx+)\3+$))xx)x)*
Try it online!
This is a direct port of the Perl/Java/PCRE regex.
Regex (.NET), 35 bytes
^(?=(x*?(?!(xx+)\2+$)x)*x)(?<-1>x)*
Try it online!
This uses the .NET feature of balanced groups to do the counting. It does not return a value for zero, but doing so only requires +1 byte (36 bytes):
^(?=(x*?(?!(xx+)\2+$)x)*x|)(?<-1>x)*
Try it online!
^ # tail = N = input number
(?=
(
x*? # Advance as little as necessary to make the following match
(?!(xx+)\3+$) # Assert tail is not composite
x # Eliminate the false primality positive of 0, and advance forward
# so that the next prime can be found (if we didn't do this, the
# regex engine would exit the loop due to a zero-width match)
)* # Every time this loop matches an iteration, the capture group 1
# match is pushed onto the stack. This (balanced groups) is how we
# count the number of primes.
x # Eliminate the false primality positive of 1
| # Allow us to return a value of 0 for N=0
)
(?<-1>x)* # Pop all of the group 2 captures off the stack, doing head += 1
# for each one. This gives us our return value match.
I strongly suspect this function is impossible to implement in ECMAScript regex, even with the addition of (?*) or (?<=) / (?<!). There doesn't seem to be room to multiplex the count and the current prime into a single tail variable, but I don't know if this can be proved.
Only one variable can be modified within a loop, such that must decrease by at least 1 on every step – and only \$O(n)\$ space is available; no variable may contain a value larger than \$n\$, and the language has no concept of arrays (although it is possible to take them as immutable input), only scalar variables (i.e. capture groups and the cursor position).
So it would seem that calculating this function would require \$O({n^2\over log(n)})\$ scratch space, to multiplex the iteration count and current prime into a single number. While multiple loops in a row would be able to get closer to \$\pi(n)\$ than a single loop, the number of such loops could only be a constant; it seems that it would need to be able to grow with \$n\$ to be able to actually asymptotically calculate \$\pi(n)\$. And a nested loop would still have to distill all the information gained by its innermost loop into a single number \$\le n\$.
But these things are just indications and vague evidence, not a proof. I have set a bounty regarding this open question.
