20
\$\begingroup\$

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 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):

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!

Improve this question
\$\endgroup\$
10
  • \$\begingroup\$ If I'm understanding this correctly, you're asking us to test for primality using only RegEx. If so then this is a dupe of our catalogue primality testing challenge which has at least one RegEx solution. \$\endgroup\$
    – Shaggy
    Jun 26, 2021 at 20:20
  • 4
    \$\begingroup\$ Indeed. The only other thing setting this challenge apart is that you only need to test numbers up to 3 digits and you're allowed to make 100 wrong outputs at most. \$\endgroup\$
    – AndrewTheCodegolfer
    Jun 26, 2021 at 20:30
  • \$\begingroup\$ Where's Martin Ender when you need him? \$\endgroup\$
    – AviFS
    Jun 26, 2021 at 20:32
  • \$\begingroup\$ Which was the only reason I didn't dupe hammer this, @AndrewTheCodegolfer; 'cause RegEx is tetchy enough that the upper bound of 1000 might actually lead to significantly different solutions. \$\endgroup\$
    – Shaggy
    Jun 26, 2021 at 21:05
  • \$\begingroup\$ @Shaggy the approaches that can be used to test for primality using regex given a decimal representation of a small integer, with 90% precision, are completely different from those that can be used given an unary representation... A deterministic test for primality using regex given a decimal representation is almost certainly impossible. The only thing these questions have in common is the word "prime". \$\endgroup\$
    – the default.
    Jun 27, 2021 at 5:59

6 Answers 6

Reset to default
24
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ @Arnauld Did you copy it into a string without escaping the backslash? \$\endgroup\$
    – m90
    Jun 26, 2021 at 14:37
  • \$\begingroup\$ Oh, of course. Sorry about that. \$\endgroup\$
    – Arnauld
    Jun 26, 2021 at 14:39
  • 1
    \$\begingroup\$ small improvement |1$ can be removed using \d+ instead of \d* adding 7 in the last set saving 2 bytes. \$\endgroup\$
    – Nahuel Fouilleul
    Jun 26, 2021 at 18:17
  • 1
    \$\begingroup\$ 69: ^(?!([258][0369]*[147]|[147][258]|[147]{3}|[0369])*$|32|62)\d+[1379]$ \$\endgroup\$
    – tsh
    Jun 28, 2021 at 4:07
7
\$\begingroup\$

 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!

This matches 68 prime numbers and nothing else.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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! 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! Link is to test suite that counts the number of matched prime numbers.

Try it online! Link is to test suite that counts the number of correctly matched integers.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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])
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ It'd be really neat if you put a link to the code you used to generate this! Super cool answer. \$\endgroup\$
    – AviFS
    Jun 27, 2021 at 21:21
  • \$\begingroup\$ @AviFS I will do this in a few days; unfortunately, the work depends on some private bugfixes to public code, so people wouldn't be able to reproduce the steps currently. \$\endgroup\$
    – Kaz
    Jun 28, 2021 at 2:19
  • \$\begingroup\$ Although not the shortest code, I like this one because it's very easy to read and the generation of the code used other code. \$\endgroup\$
    – RockPaperLz- Mask it or Casket
    Jun 28, 2021 at 10:44
  • \$\begingroup\$ Erratum: the first character count had been incorrectly given as 529. \$\endgroup\$
    – Kaz
    Jun 28, 2021 at 13:13
3
\$\begingroup\$

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!

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 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!

Similar to the one below, but optimized by a simple program I wrote similar to https://github.com/noprompt/frak

JavaScript (Node.js), 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!

contains 152 of the 168 prime numbers under 1000 ~90%

cant get simpler can it?

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.