[Question]
  [
This time, you are working on a regex. Your regex is meant to approximately full-match the base-10 representations of primes \$0 \le p < 1000\$, while ignoring any non-numeric string or composite in the range. You can full-match 2, 53 or 419, but not 0, 82 or example.
The approximately is important -- a minimum of **900** numbers have to produce the right output. You can match more numbers correctly (but as this is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") challenge you probably shouldn't). For clarification, how numbers above 1000 are matched **doesn't matter** and they can produce whatever output you like.
Test cases part 1, strings which should be matched ([primes under 1000](https://www.infoplease.com/math-science/mathematics/numbers-formulas/prime-numbers-between-1-and-1000)):
```
5
739
211
617
103
503
11
13
17
23
71
89
257
```
Part 2: strings that shouldn't be matched
```
five
5o
2q11
716
102_3
42 + 1
term in A000040
16
204
```
Your score is the number of characters in your regex. Lowest score wins. Have fun!
  
[Answer]
# ~~90~~ ~~79~~ ~~72~~ ~~67~~ ~~65~~ 64 bytes
`^(?!([258][0369]*[147]|[1475][258]|[147]{3}|[0369])+$)\d+[1379]$`
Matches 2–3-digit numbers not divisible by 2, 3, or 5, with an added bit (the `5` in `[1475]`) that removes 8 false positives (527, 529, 551, 553, 559, 581, 583, 589) and adds 4 false negatives (521, 523, 557, 587).
-2 thanks to Nahuel Fouilleul; -9 by removing `[258]{3}`, which was not necessary; -7 by removing one `[0369]*`; -5, -2, -1 with successive improvements on an idea from tsh.
[Answer]
# ~~101~~ 96 bytes
This is manually optimized and probably sub-optimal.
```
^((10?|19|82)[1379]|(31|46?|64|88)[137]|(6?5|8|17|23?|26|3[578]|44|5[069])[39]|(22|61|85)[379])$
```
[Try it online!](https://tio.run/##bZJNbxMxEIbv@RVLBW1WccP626ZEOcERVVyjoEbpEi0K2SgbKiTMbw/PhFJRxGG09qzfd54Z@8vqYTWsD93@eL3r79tTW82qj@3m3ff9@O70aTzWzbzoXJKpF9rGvCxjq4sL8xJcSemcJBfmvqSiYzF2XkwoduFjWhbnil80IS/rhRWpMSXokjxbrOqXp7vpsO3W7Vir6lrX9Wi0P3RfBWFhlFVeRaW10lZpFlkZq0xWVisbldPKWeWi8pzLKmgVoopaRatiVsmqlFVG1aBvMGhknbFjbVhb8ZUvOUd49p594D9OOkpR8ol8lmAvfhkMmIyw4GOMYLHGx8BkvAR5fEwgB5KJ7PExSfitsrBYPCwsls6sdASLdRI0SEuWniwcFg5mpSxaS0sWBkdPjl4cI3FG5iDBMGBwMhQ8HAyOoTg4HD4OD5f40oujB89MPB4evacXD7uXaaLzaDzsHnYPu0fns4yZOVM7wB9gD1q@5KgfnAQ5PAL8Qe7kfCms8QjwB2rHRiJzUwTzi3BHuCPayOwi9SO6SP0od0ntSM8JTWJmyUhwu2iTkYsmqJfQJWom2BP1EvNO8grQZ3gz2kzNjCYz6wxvhjWjzcwn02tGl9FkOHOOy5vR6PNqO7S3/cCLPC8/tBuWjfzpD@Nh3R/kse7OOT5vK900sppM6urHqKq64fbxQZ8f9rTbrbff7tthvKtv@P3bYDKr2umxHY5kq9nsj0gOPNV/dubysnrx7yEh49CLZ6eeDv0crfvd0G/b6bbfPHK/BraaVFevrmD5@/fFezGs9v3QHbuH9s2FeuL4/8ldu1k9OwlMfXP6BQ "JavaScript (Node.js) – Try It Online")
This matches 68 prime numbers and nothing else.
[Answer]
# 69 primes, 831 composites, 83 bytes
```
^((3+|46?|60?|1[0359]?|75|9[479])[17]|(3?[78]|6?[15]|[15][069]|2[236]?|4[34])[39])$
```
[Try it online!](https://tio.run/##FYsxDsMgEAT7@0XEWQIjRcZgCBVlqrzgjCFSXKRJEaW8d@UB@RjBxa52pNn3/nm@7g1ijDj@vgB4rjDIa22blFaz84n9lNjQZJeYE4eFI7kQsyITMkubKFwy@0RmyXwUTT5mnmm2vvuOrOuu7QdsOApQdX1owLHAcKsb8lZ6ZClarUYfM52kEJ1mjUqAaX8 "Retina 0.8.2 – Try It Online") Link is to test suite that counts the number of correctly matched integers. (The composite number that it incorrectly detects as prime is 169.)
# 68 primes, 832 composites, 85 bytes
```
^((31?|46?|60?|1[0359]?|75|9[479])[17]|(1[079]?|2[236]?|5[069]?|73?|82?|3[578])[39])$
```
[Try it online!](https://tio.run/##HZK7jhxBCEVzfmNtaTbr4lFA1OF@RGusdeDAiQPLYf/7@LABqiqmLxwu8/fXv99/fr6@Pz4@Xz8eD1vn7fu893He6zos@nneGXdfnv18v1Y@7wc/5OT1UtuccR376zs779Lztiuy@NhQfHu9yfvHp7y9VExCUtaSZbK4tKiJttgSS/ElbuIpwXcte8lOySVpki1lUi2N6kB/UOCYe1OOu3K3qTsnOSeCd/De/E6lldOUfJHvCd5Tr8GASYeFOqqDxZ06CpPGBHnq6CYHkiZv6mgNv4nBYtQwWIzJbCaCxXyCARkJK8XgMDgMDkNrjGQwODM5sziWuI4PE5gBg48p1HAYHFMcDqcO@xAvTmZxZgg8CWoE@mCWgD3GTXSBJmAP2AP2QBc9NuMzvTf8G/a95iRH/@0T5Kix4d@zk6@lcKfGhn/TO4@JZlME/iXcCXeiTbxL@ie6pH/OLumdzFxoCs9KJ9gu2tJZNEG/Qlf0LNiLfoXfNf8C9A1vo216NprG64a3YW20jT/NrI2u0TSc3fkf "Retina 0.8.2 – Try It Online") Link is to test suite that counts the number of matched prime numbers.
[Try it online!](https://tio.run/##HUs9DsIgFN7fLQzPBEpiChQo0xudPAFtwUQHFwfj@M7lAbwYUocv3//r/n48rw1SSjh8PwB4qnCU59o2KZ0hngJxGIlNHp1PK3H0nPIU06qyiSvLXsQ9t9m60NnnMfx3jni2xC77OPex6w9sOAhQdblpwKHA8VI35K10yFK0WozeJR2kEN1ZjUqAaT8 "Retina 0.8.2 – Try It Online") Link is to test suite that counts the number of correctly matched integers.
[Answer]
# Classic regex, ~~526~~ 452 characters.
```
9(9(7|1)|83|7(|7|1)|67|53|4(7|1)|37|29|1(9|1)|07)|
8(9|8(7|3|1)|77|63|5(9|7|3)|3(|9)|2(9|7|3|1)|11|09)|
7(|9(|7)|87|73|6(9|1)|5(7|1)|43|3(|9|3)|27|1(|9)|0(9|1))|
6(91|83|7(|7|3)|61|5(9|3)|4(7|3|1)|31|1(|9|7|3)|0(7|1))|
5(|9(|9|3)|87|7(7|1)|6(9|3)|57|4(7|1)|3|2(3|1)|0(9|3))|
4(9(9|1)|87|7(|9)|6(7|3|1)|57|4(9|3)|3(|9|3|1)|21|1(|9)|0(9|1))|
3(|97|8(9|3)|7(|9|3)|67|5(9|3)|4(9|7)|3(7|1)|1(|7|3|1)|07)|
2(|9(|3)|8(3|1)|7(7|1)|6(9|3)|5(7|1)|41|3(|9|3)|2(9|7|3)|11)|
1(9(|9|7|3|1)|81|7(|9|3)|6(7|3)|5(7|1)|49|3(|9|7|1)|27|1(|3)|0(9|7|3|1))
```
**This is non-competitive answer for reference, giving the accurate match.**
Two more bytes `^...$` may be needed in a given implementation language/utility to anchor this.
In POSIX world, this is an "extended" regex (ERE); a basic regex (BRE) requires escaped parentheses, otherwise they are literal.
This was calculated by creating a trie structure out of the data set, applying path compression, and then converting to regex.
This can be improved by reducing patterns like `(9|7|3|1)` into `[9731]` character classes, and empty branches `(|3)` into `3?` and such:
```
9(9[71]|83|7[71]?|67|53|4[71]|37|29|1[91]|07)|
8(9|8[731]|77|63|5[973]|39?|2[9731]|11|09)|
7(97?|87|73|6[91]|5[71]|43|3[93]?|27|19?|0[91])?|
6(91|83|7[73]?|61|5[93]|4[731]|31|1[973]?|0[71])|
5(9[93]?|87|7[71]|6[93]|57|4[71]|3|2[31]|0[93])?|
4(9[91]|87|79?|6[731]|57|4[93]|3[931]?|21|19?|0[91])|
3(97|8[93]|7[93]?|67|5[93]|4[97]|3[71]|1[731]?|07)?|
2(93?|8[31]|7[71]|6[93]|5[71]|41|3[93]?|2[973]|11)?|
1(9[9731]?|81|7[93]?|6[73]|5[71]|49|3[971]?|27|13?|0[9731])
```
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 405 bytes
```
1(0[1379]|13?|27|3[179]?|49|5[17]|6[37]|7[39]?|81|9[1379]?)|2(11|2[379]|3[39]?|41|5[17]|6[39]|7[17]|8[13]|93?)?|3(07|1[137]?|3[17]|4[79]|5[39]|67|7[39]?|8[39]|97)?|4(0[19]|19?|21|3[139]?|4[39]|57|6[137]|79?|87|9[19])|5(0[39]|2[13]|3|4[17]|57|6[39]|7[17]|87|9[39]?)?|6(0[17]|1[379]?|31|4[137]|5[39]|61|7[37]?|83|91)|7(0[19]|19?|27|3[39]?|43|5[17]|6[19]|73|87|97?)?|8(09|11|2[1379]|39?|5[379]|63|77|81|9)|97
```
[Try it online!](https://tio.run/##TZCxbsMwDET3fkVHaWhgmpZpDYWm/kBXwUCC1AlSJHaQBEkH/rtLUoWbxZDEO97zfW/um@v2cjjf3sbpa5h37@sZXJUBKfYMmLgmxgxyS9xEDnLsuc0oX8qorx1wLPrkuXYAXGdzY5k38O@K6tJzJ46eIyafGF1FDLpC1GjjJuuCYIaWliS7RxJPo4xKGIUQ1FWyTBFIssAQZdyR8sXecxCTzmsLR1FrlqmfyFSuyySl1RR5A/shgQP16OI/NFA0xe6QI3imZyxaGsClAR0SWghpQueqyFZZaRzFGEp9LTKRtetFPK9fttN4nY7D6jjt3Tg8Xj@H/cfP2e1Wt8vh5Lz38y8 "JavaScript (Node.js) – Try It Online")
Similar to the one below, but optimized by a simple program I wrote similar to <https://github.com/noprompt/frak>
---
# [JavaScript (Node.js)](https://nodejs.org), ~~578 bytes~~
```
2|3|5|7|11|13|17|19|23|29|31|37|41|43|47|53|59|61|67|71|73|79|83|89|97|101|103|107|109|113|127|131|137|139|149|151|157|163|167|173|179|181|191|193|197|199|211|223|227|229|233|239|241|251|257|263|269|271|277|281|283|293|307|311|313|317|331|337|347|349|353|359|367|373|379|383|389|397|401|409|419|421|431|433|439|443|449|457|461|463|467|479|487|491|499|503|509|521|523|541|547|557|563|569|571|577|587|593|599|601|607|613|617|619|631|641|643|647|653|659|661|673|677|683|691|701|709|719|727|733|739|743|751|757|761|769|773|787|797|809|811|821|823|827|829|839|853|857|859|863|877|881
```
[Try it online!](https://tio.run/##HZExbgJBDEX7nCIlFEE7Y3s8U6TMBXICEAFERAABSlL47pvnFNZ6DP/72f7cfG/u29vx@ng5Xz528/51PdeQsPAoJYpEIRlRJeoIKSEeWkIl1MP434hWonl4CZfwEV2ijxioJvQTBlPmAzvySi7pm19qShhv4934Hafi2ZR6pz4yeKffAAOmmiz41JpY5PhUmKplUMenNmogVeeNT@3JLyGwCB4CizCZ5ESwiGYwICMJMwkcAofAIWiFkQQGZSZlFmUlWnMPGSwDBs2l4KEwKEtROBQfxUM7X2ZRZjB2YngYemMWg91ym@gMjcFusBvshs5Grpk907vB32BvJb/U6N80gxoeDf6WN/k/CjkeDf5Gb58yBpci2J/D7XA7Wmd3Tn9H5/T3vCW9nZk7ms7Oes3gumh7zUMT9OvoOj077J1@vZd5/bS9nO@X0251uhwW593P8/vu8PZ7XexXj9vxa7FcLuc/ "JavaScript (Node.js) – Try It Online")
contains 152 of the 168 prime numbers under 1000 ~90%
cant get simpler can it?
[Answer]
# Any flavor, 148 bytes
```
^([389]?113?|2(39?|2[379]|[147]1|[9862]3)?|(1[023569]?|4[568]?|6[147]?|9[03469]?|3[013469]?|8[8572]|7[259]|5[4578]|)7|1?[357]|[258]9|[37]1|[4785]3)$
```
[Try it online!](https://tio.run/##LZLLaiMxEEX3/gotBtINItNS6VWB4FW@oumBTHASg1@0HZghnW/3nHJmUZZU7nvrVEmnv5f340Haab5et/vTcb64ebM6zdv95vz4Gb347KsPwQfxgY36KD6ql@Cl@hR8Ep@qz3ynvgRfqq/BV/FVfRPf1CuqAf2AwWB7xY59ZC/mayu5RGTOmXPhf5xCtaLkG3m14Gx@CgZM0VjwidGw2OMTYYrZgjw@sZADKVbO@MRm/OIFFsFDYBE6E@sIFkkWNEhLQk8Ch8AhcAhaoSWBIdFTopfESFK0OVgwDBiSDQWPBENiKAmOhE/CIzVWekn0kJlJxiOjz/SSYc82TXQZTYY9w55hz@iy2piZM7UL/AX2EmwlR/2SLMjhUeAvdie3S2GPR4G/ULsOFspNEcyvwl3hrmgrs6vUr@gq9avdJbUrPTc0jZm1aMHtom3RLpqgXkPXqNlgb9RrzLvZK0Cv8CpapaaiUWat8CqsilaZj9KrolM0Cqdq/VqtVq/HmUf5tvnjtge3fz5158t8T2xP3h1Pm0M39P3Dyj25Rzf@Ph533by5f/3Y7fbPl5f37qb0ju@7bd/37vHRdVtz@n7kvTP7W2J@PrxtujAMQz@t3PnlOG@wPH/su6fe/XQ7Kj31K9MdLt3r3TfS5235enCfN8HXXX@9/upGnsm05p2vl9iJ8jvygKZlDKlOYRm1lThJv166MA5RuOhpvaQxl8Zabl@tFx0HSbd/ZBzC/20bmXKcljrGjGEeeWRtWvq6hPUouVIj5jbpQkGrlCon6X/8Aw "Python 3.8 (pre-release) – Try It Online")
Matches 68 of the 168 primes between 0 and 1000 as being prime, and all 832 of the composites, totalling 900, or 90% of the total 1000.
[Answer]
# .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!](https://tio.run/##RZDhboIwFIVfhZEm9obVgEMcYkGz33sCZAlxdTSphUCNi6XPzlqd25@bnK/nnp7crr2wfmiYEBPqadmzL/ZdrdeSXfB2Nn3g4gkXGONiQ@Icg45CAyPoNDWOxWSR32VocEHLhKSVwznoxEDh0AtZ/rEXx8rF8vUXjGUUryooYA4Bst8sYcT7xHrAeiObiGOwI7FjsyNJfm8Bj1enE7LLAe9jKMYbBR3bbvvVWIZRhWCabZ/9t/bUccE@fcjQlYbZse1ZfWgwEh6XHuKyOyvQqKZIkKETXPnEz/gRo3p@aM9SEaG8hTMEFNVlWBkbgJGkJZequpEMSSLYQ0dOBwFol3GiqJ@/1@rQsMEuwZ1eQV96rhhp2kEZ2yrK/rVHZGvvL7hkno@kb4yZQpKm6Q8 "PowerShell – Try It Online")  
[Try it online!](https://tio.run/##VVJtb5swEP4rCFmqrYyKwwHjIpRK@7xfgDIJZe6C5JqIUGVqjt@e3Zmm6775Xp6Xe@A0Xtx0Pjrvb2Jqu8n9dn/2T0/BXeTzw@2ntNJ2BvZYazT82GFlsNS4jV1tsLAInaV3bhTW0mLdGU2lMVhpLDtrNO3ZHRb8pAEA5lahkdbssDZoNFaRoIyUW426s5qECoNAuJyHinSlhQ8bPK2AyYl7u@ppYB9xlDORwpKsRyIWidxVBJTm7p48MTTnNilsGcC30j4JVytxXGcc2@IACvjiCzXdQTfzglnlOKAPZ9YwjLUgku04JWKQVpOtKP6fszUB@ExgTQ@AMMDmVo4aPqU4izvMMix@Ik5OR4cMUErcHp6/pd/H19Pg3a9UNeK9zZuXcXL94SiFT4aQiCGc3mZ1FX0rfHY@@WFOs7QZXqToHw/jW5gzPycFL2xa0Xf5fiECKULbDWHex04jQubdvQauNxt1ZY7XVkyPP/r5cHRnAqm1@66ul2mYXXYcz/NCrqD5VydZGOk/9ENwSSpCuizLLc@stX8B "PowerShell – Try It Online") - [Kaz's 456 byte POSIX ERE compatible solution](https://codegolf.stackexchange.com/a/230608/17216), for comparison  
[Try it online!](https://tio.run/##RY/RaoQwFER/xYYLJs1m0b65Enahz/0CayHYuzWQvZGYxbDit1ttKX08M8MwM/gJw9ijcysE3QT8wtSeToQTv@TrBz8/8ZSkeC8liJTW/HJgr/42WIefTNTw0EV99QFN13NwmaUMLA33KGYwGpwaB2cjU6y2Vw7m2Pk7ReVi9rIHpAbTFO2yFXAg3ViK7Y9SAymHf1zuLKWY946bhnB8M7HrceR5yp@BxK/zEPMUbETV@zEu27Ky/udMkd8@OUuYMSC2LMtaqKqqvgE "PowerShell – 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](https://codegolf.stackexchange.com/a/230608/17216) 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](https://codegolf.stackexchange.com/questions/150534/a-regex-to-match-three-consecutive-integers-iff-the-third-integer-is-the-sum-of/150631#150631) 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](https://codegolf.stackexchange.com/questions/57617/is-this-number-a-prime/260450#260450).
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!](https://tio.run/##RZHRboIwFIZfhZEm9oTVgEDdRKhm13sCZAlxdTSphUCNi9Bnd@3U7eYk39fTc/60XXvm/dBwKa@oz8uef/HvarVS/Iw3s@sHZk@YYYzZmiQFhjEKDUwwxnFsnEzIorhzaDDLS0peK@cLGKkB5lRM0j8XO1cu0pe7mMooWVbAYA4BsotSmPCO2h6AMbUrGE7AFmrLektoccsBj1PHlGwLwLsE2PRrbUZKl2a3nMowqhBcZ5tn/609dkLyTx8ydMnD7ND2vN43GElPKA8J1Z00jKjOkSRDJ4X2iZ@JA0b1fN@elCZSewvXEOSoLsPK2AEYqbwUSle/JkOKSP7gyHEQwOhmHHPUz99rvW/4YC/BzV5gPPdCc9K0gzY2VZT9s0dUa79ACsU9HynfGHMNiX3l@Ac "PowerShell – 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!](https://tio.run/##RZHhaoMwFIVfxUmgubgUbbVtatXCfu8J1IG4dAbSKJrSUc2zu6Tduj8XznfPPTmQrr2yfmiYEDPqk7xnX@y73O8lu@LjYv7AWYIzjHF2IGGKYQx8DROMlGrLQrJKH9LXxplvCC0tTmHcaMgsWpPoydaW5ato9wumPAi3JWSwBA@ZZzYw4QkDGGdg8nAIZkRmHCiJ0keH59bqiNAUcEFNbBFCNt1XMIamXrEzdy/FFubF8dV9a88dF@zThRjdEj8@tT2r6gYj4XDpIC67i4IRVQkSZOgEVy5xY37CqFrW7UUqIpSzsgYvQVXul9oEYCSTnEtV3kmMJBHsTwdWex6MNuOcoH75Xqm6YYM5gge9wXjtuWKkaQelTasg/tcOka35AsElc1wkXa21M/uEUvoD "PowerShell – 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 / Python[`regex`](https://github.com/mrabarnett/mrab-regex) / 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).
]