.NET regex, 236 229 222 210 202 198 192 bytes
^(?!(?(((?<-4>(){10})|){99}((?<4-2>)|){990}(?=[6-9](?<4>){6})?(?=[3-59](?<4>){3})?([258](?<4>)|[147])?).)+$(?(5)|(\6)?()){31}(?(4)(?(6)(?<A-6>(?<-4>))){31}(?>(?<6-A>)(\4)?|){31}){499}\7|[01]$)
Try it online!
Try it online! - Kaz's 456 byte POSIX ERE compatible solution, for comparison
Try it online! - primes matched in unary, for comparison
This correctly identifies all \$168\$ primes and \$832\$ non-primes in the range \$[0,999]\$. (Processing that entire range on TIO takes 30 4 seconds.) As such it competes in the 100% category, as one other answer to this challenge has done, and not 90%-or-better as the challenge asks for.
Earlier versions of this were split into two levels of golf, one running in a reasonable amount of time, and the other experiencing exponential slowdown (being probably too slow to finish processing the entire range before the heat death of the universe). But since the 194 byte mark was reached, that version became obsolete, and now the shortest version is approximately equal in speed to the fastest version.
-8 bytes (210 → 202) by using a variant of jimmy23013's digit capture technique instead of binary
The primary challenge here is that a regex can only do its work within the space of the input. In unary, this is no problem as far as matching primes go. But in decimal, the digits don't provide enough space to do the necessary computational work – numeric variables cannot be stored in the form of captured portions of the input string, as the number of possible states of each such a capture, including the unset state, would only be \$n({n+1})/2+2\$ at best (if every digit is unique), or \$n+2\$ at worst (if all digits are identical), when it needs to be \$10^n\$ – where \$n\$ is the number of decimal digits in the input.
This regex uses .NET's Balanced Groups feature to do its magic. In .NET, each time a capture has been made to a particular group, using (...) or (?<n>...), it is pushed onto that group's capture stack, which retains the full information of every substring contained in that stack, in order. That's overkill in this case, as this regex only pushes empty strings* onto the capture stacks. Each emulated numeric variable is stored as the number of times a capture has been pushed onto the stack of a particular group. (Popping is done using (?<-n>...), which asserts the stack is non-empty and removes the capture at the top of that stack – as well as matching the enclosed pattern, which can be unrelated. As far as this regex is concerned, it simply asserts that the variable is nonzero and then decrements it.)
*Not that it makes any difference given how the regex works, but following the 210 → 202 golf, if the last digit of the input is in [124578], the topmost capture on the \4 stack will contain that digit. The rest are empty.
But even with this trick, it is impossible to do unbounded arithmetic. A repeated operation (incrementing and/or decrementing a capture stack variable) can only be either done as many times as there are characters in the input, or done a hard-coded maximum number of times. These can be combined and multiplied, but that still only means it could be repeated a number of times that is proportional to a polynomial function of the input string's length, whereas to be able to scale with decimal input (or any base besides unary), it'd need to be an exponential function.
So at the time of this posting, I had thought it impossible to match all primes up to infinity in decimal with a pure regex. But it turns out to be possible after all, by doing base-encoded arithmetic and long division; that regex is much longer.
In the commented explanation below, I use the shorthand Cn to signify the capture count of group \n:
^ # Anchor to start
(?! # Negative lookahead - assert that none of the following two
# alternatives can match.
# Match any composite number in decimal
# Parse the number, translating decimal into the capture count C4
(?( # This entire section is wrapped inside a lookahead conditional,
# which just acts as a golfed lookahead since it always matches.
((?<-4>(){10})|){99} # C2 += C4 * 10; C4 = 0
((?<4-2>) |){990} # C4 += C2; C2 = 0
# Read this digit, adding it to C4
(?= [6-9] (?<4>){6})? # C4 += 6, if digit is in [ 6789]
(?= [3-59](?<4>){3})? # C4 += 3, if digit is in [ 345 9]
( [258] (?<4>) | # C4 += 2, if digit is in [ 2 5 8 ]
[147] )? # C4 += 1, if digit is in [ 1 4 7 ]
)
. # Consume digit
)+$ # Loop until all digits have been read.
# C6 = any number from 2 to 31 (31 is the largest prime ≤ sqrt(999))
(?(5)| # Conditional - On each iteration, only do anything if \5 is
# unset.
(\6)? # On any iteration after the first, \5 can be set, which
# signals that no further iterations after the next will
# increment C6. Doing it this way ensures that C6 will be
# incremented at least twice.
() # C6 += 1
){31} # Iterate 31 times, to give C6 a possible range from 2 to 31.
# We can't accomplish this as "{2,31}" because then .NET,
# like Perl but unlike PCRE, would only do the minimum number
# of iterations (i.e. 2) before exiting the loop due to a
# zero-width match.
# Divide C4 / C6, enforcing that the remainder is zero. The quotient is the
# number of iterations that start with C4 != 0, i.e. the number of non-NOP
# iterations.
(?(4) # Make each iteration of this loop conditional upon C4 != 0, so
# that if the division finishes and C4 is still nonzero, the
# loop will fail to match and will immediately backtrack to try
# a different value of C6; this provides a huge speedup,
# relative to putting "(?!\4)" after the end of the loop (which
# would can't do anyway now, since it doesn't always capture
# empty strings). Thus, the loop can only finish and exit if
# C4 == 0 after the division has completed, which, if C7 ≥ 2,
# means that C4's original value was composite.
# Total effect of the following loop: C4 -= C6; CA = C6; C6 = 0
(?(6) # Make each iteration conditional upon C6 != 0, so that
# this loop can't finish without fully subtracting C6
# from C4. If C4 was less than C6, this loop will fail
# to match before it can finish, and the regex will
# backtrack to try a smaller value of C6.
(?<A-6>(?<-4>)) # CA += 1; C6 -= 1; C4 -= 1
){31} # Do the above the maximum of up to 31 times,
# the maximum value that C6 could have had.
(?>(?<6-A>)(\4)?|){31} # C6 = CA; CA = 0;
# \7 = set if C4 != 0, i.e. if quotient ≥ 2
){499} # Handle a quotient of up to floor(999 / 2)
\7 # Assert that the quotient was ≥ 2
| # or...
# Match the decimal numbers 0 or 1
[01]$
)
This algorithm can do \$[0,3333]\$ in 56 seconds on TIO (the regex becomes 195 bytes): Try it online!
Here is an alternative 195 byte version that does not do any direct matching against the digits after their initial reading. I'm including this not just because it's an interesting variation of the algorithm, more like ^(?>(x(x*))\1+$)\2 whereas the above version is like ^(?!(xx+)\1+$)xx, but because it just might be possible to golf to a shorter length than the above version.
^(?=(?(((?<-4>(){10})|){99}((?<4-2>)|){990}(?=[6-9](?<4>){6})?(?=[3-59](?<4>){3})?([258](?<4>)|[147])?).)+$(?(6)|(|())){31}(?(4)(?(5)(?<9-5>(?<-4>))){31}(?>(?<5-9>)(\9)?(\4)?|){31}){499}\8)(?!\7)
Try it online!
^ # Anchor to start
(?= # Atomic lookahead
# Parse the number, translating decimal into the capture count C4
(?( # This entire section is wrapped inside a lookahead conditional,
# which just acts as a golfed lookahead since it always matches.
((?<-4>(){10})|){99} # C2 += C4 * 10; C4 = 0
((?<4-2>) |){990} # C4 += C2; C2 = 0
# Read this digit, adding it to C4
(?= [6-9] (?<4>){6})? # C4 += 6, if digit is in [ 6789]
(?= [3-59](?<4>){3})? # C4 += 3, if digit is in [ 345 9]
( [258] (?<4>) | # C4 += 2, if digit is in [ 2 5 8 ]
[147] )? # C4 += 1, if digit is in [ 1 4 7 ]
)
. # Consume digit
)+$ # Loop until all digits have been read.
# C5 = any number from 1 to 31 (31 is the largest prime ≤ sqrt(999))
(?(6)| # Conditional - On each iteration, only do anything if \6 is
# unset.
(|()) # C5 += 1; if this chooses to set \6, then for the rest of the
# loop, C5 will no longer be incremented. This has the effect of
# trying values in the order from 31 down to 1.
){31} # Iterate 31 times, to give C5 a possible range from 2 to 31.
# We can't accomplish this as "{2,31}" because then .NET,
# like Perl but unlike PCRE, would only do the minimum number
# of iterations (i.e. 2) before exiting the loop due to a
# zero-width match.
# Divide C4 / C5, enforcing that the remainder is zero. The quotient is the
# number of iterations that start with C4 != 0, i.e. the number of non-NOP
# iterations.
(?(4) # Make each iteration of this loop conditional upon C4 != 0, so
# that if the division finishes and C4 is still nonzero, the
# loop will fail to match and will immediately backtrack to try
# a different value of C5; this provides a huge speedup,
# relative to putting "(?!\4)" after the end of the loop (which
# would can't do anyway now, since it doesn't always capture
# empty strings). Thus, the loop can only finish and exit if
# C4 == 0 after the division has completed, which, if C7 ≥ 2,
# means that C4's original value was composite.
# Total effect of the following loop: C4 -= C5; C9 = C5; C5 = 0
(?(5) # Make each iteration conditional upon C5 != 0, so that
# this loop can't finish without fully subtracting C5
# from C4. If C4 was less than C5, this loop will fail
# to match before it can finish, and the regex will
# backtrack to try a smaller value of C5.
(?<9-5>(?<-4>)) # C9 += 1; C5 -= 1; C4 -= 1
){31} # Do the above the maximum of up to 31 times,
# the maximum value that C5 could have had.
# Total effect of the following loop: C5 = C9; C9 = 0
# (as well as the possible setting of \7 and/or \8)
(?>
(?<5-9>) # C5 += 1; C9 -= 1
(\9)? # \7 = set if C9 == 0, i.e. C5_initial ≥ 2
(\4)? # \8 = set if C4 != 0, i.e. if quotient ≥ 2
|
){31}
){499} # Handle a quotient of up to floor(999 / 2)
\8 # Assert that the quotient was ≥ 2
)
(?!\7) # Assert C5_initial == 1, i.e. that the largest divisor
# resulting in a quotient ≥ 2 was 1
It should also be possible to implement a finite-bounded primality test in regex flavors that don't have balanced groups, but do have persistent backreferences (Perl / Java / Pythonregex / Ruby / PCRE); it would have to be done in emulated binary, so there'd have to be a capture group for each bit, at each location where emulated addition/subtraction is done – which means \$10\$ of them for each variable at each arithmetic location to handle \$[0,999]\$, and each one would have to implement its own copying and carry/borrow in each addition/subtraction operation – so, such a regex would probably be enormous, and would likely only pass the breaking-even point against POSIX ERE at a larger maximum range of handled primes (maybe one more decimal digit would be enough, or maybe not).
