Regex (Perl / PCRE), 55 54 53 bytes
^(?=((?=((\2x*?|^)((?!(xx+)\5+$)))xx)x)*(x*))\6(?4)xx
Try it online! - Perl
Try it online! - PCRE
Takes its input in unary, as a string of x
characters whose length represents the number. Based on Prime counting function.
^ # tail = N = input value
(?=
# Calculate π(N) = the number of primes <= N, by counting
# 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. 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.
| # or
^ # Don't advance at all on the first iteration
# (when \2 is is still unset), so as to assert
# that N is not composite.
)
((?!(xx+)\5+$)) # Define and use subroutine (?4): Assert tail
# is prime. 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 smaller primes
# remaining.
# At this point, head = π(N), and tail = N - π(N)
(x*) # \6 = tail = N - head = tool to make tail = head
)
\6 # tail = π(N)
(?4)xx # Assert tail is prime
Alternative 55 54 53 bytes:
^(?=((?=((\2x*?|^)((?!(xx+)\5+$|x?$))))x)*(x*))\6(?4)
Try it online! - Perl
Try it online! - PCRE
This eliminates the false negatives \$0\$ and \$1\$ in the definition of the primality subroutine instead of patching its second and third individual uses.
Regex (.NET), 70 60 58 bytes
^(?=(\3*?(?!(xx+)\2+$)(x))*x)(?<-3>x){2,}(?<!\3|^\4+(x+x))
Try it online!
This uses the .NET feature of balanced groups to do the prime counting. Since .NET regex has no subroutines, this has three two copies of the primality test.
^ # tail = N = input value
# Calculate π(N) = the number of primes <= N, by counting
# from the largest to the smallest prime.
(?= # Atomic lookahead - lock in this match once it completes
(
\3*? # Advance as little as necessary to make the following
# match, but don't advance at all on the first iteration
# (when \3 is is still unset), so as to assert that N is
# not composite.
(?!(xx+)\2+$) # 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); \3 = 1, to signal the first iteration
# has been done, and push a capture onto the Group 3 stack.
)* # Loop as many times as can be done until its stops
# matching.
x # Eliminate the false primality positive of 1
)
(?<-3>x){2,} # Pop all Group 3 captures off the stack, asserting that
# the count is ≥ 2, and doing head += 1 for each one. Since
# this isn't done atomically, we need to subsequently
# verify that all captures were popped, due to backtracking
# if the following assertion fails.
(?<!\3|^\4+(x+x)) # Assert that the Group 3 capture stack is empty, and that
# head is not composite (and since it's already been
# forced to be ≥ 2, this asserts it to be prime).
Regex (Perl / Java / PCRE / .NET), 60 bytes
^(?=((?=((\2x*?|^)(?!(xx+)\4+$))xx)x)*(x*))\5(?!(xx+)\6+$)xx
Try it online! - Perl
Try it online! - Java
Try it online! - PCRE
Try it online! - .NET
This is a straight port of the Perl/PCRE version, to regex engines that lack subroutine calls but support nested backreferences. The subroutine call has been replaced with a copy of the routine.
Regex (Perl / PCRE / Pythonregex
), 61 bytes
^(?=((?=((\6x*?|^)((?!(xx+)\5+$)))xx)(?=(\2))x)*(x*))\7(?4)xx
Try it online! - Perl
Try it online! - PCRE
Try it online! - Python import regex
This is a port of the Perl/PCRE version. \2
is copied into \6
using the lookahead (?=(\2))
, since Python (even with import regex
) lacks nested backreferences.
Regex (PCRE / Ruby), 62 bytes
^(?=((?=((\6x*?|^)((?!(xx+)\5+$)))xx)(?=(\2))x)*(x*))\7\g<4>xx
Try it online! - PCRE
Try it online! - Ruby
This is a straight port of the Pythonregex
version, to Ruby's subroutine call syntax.
Regex (Perl / Java / PCRE / Pythonregex
/ Ruby / .NET), 68 bytes
^(?=((?=((\5x*?|^)(?!(xx+)\4+$))xx)(?=(\2))x)*(x*))\6(?!(xx+)\7+$)xx
Try it online! - Perl
Try it online! - Java
Try it online! - PCRE
Try it online! - Python import regex
Try it online! - Ruby
Try it online! - .NET
To be portable to all 6 regex engines, this uses neither nested backreferences nor subroutine calls.