Regex (Perl / PCRE), 55 bytes
^(?3)(?=((?=(\2?+x*?((?!(xx+)\4+$)))xx)x)*(x*))\5(?3)xx
Try it online! - Perl
Try it online! - PCRE
Takes its input in unary, as a sequence of x
characters whose length represents the number. Based on Prime counting function.
^ # tail = N = input value
(?3) # Assert N is not composite
(?=
# 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, 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+)\4+$)) # Define subroutine (?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 smaller primes remaining
# At this point, head = π(N), and tail = N - π(N)
(x*) # \5 = tail = N - head = tool to make tail = head
)
\5 # tail = π(N)
(?3)xx # Assert tail is prime
Alternative 55 bytes:
^(?3)(?=((?=(\2?+x*?((?!(xx+)\4+$|x?$))))x)*(x*))\5(?3)
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 uses.
Regex (.NET), 70 bytes
^(?!(xx+)\1+$)(?=(x*?(?!(xx+)\3+$)x)*x)(?>(?<-2>x)*)(?<!^x?|^\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 copies of the primality test.
^ # tail = N = input value
(?!(xx+)\1+$) # Assert N is not composite
# Calculate π(N) = the number of primes <= N, by counting
# from the largest to the smallest prime.
(?=
(
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
)
(?>(?<-2>x)*) # Pop all group 2 captures off the stack, doing head += 1 for each one,
# atomically so it won't backtrack to force it to match the following:
(?<!^x?|^\4+(x+x)) # Assert head is prime