4
\$\begingroup\$

Isolated prime definition from Wikipedia:

An isolated prime is a prime number p such that neither p − 2 nor p + 2 is prime. In other words, p is not part of a twin prime pair. For example, 23 is an isolated prime since 21 and 25 are both composite.

Consider strings which consists of character x repeated n times, where n ≥ 0. You shall write a regex which matches strings whose length is an isolated prime, and rejects strings whose length is not an isolated prime.

Same rule as my previous question Match strings whose length is a fourth power:

  • Any (ir)regular expression syntax is allowed, except for arbitrary code execution (to Perl users).
  • Your solution should logically1 work correctly for large number. This means that an answer that lists out all the lengths within certain range is disqualified.
  • Please also include a short explanation about your approach to the problem (something like this).

1 Some engine implements * with an upper limit. This question assumes that * doesn't have an upper limit (and the only limit is the length of the input string).

This question on SO might be useful as a starting point. How to determine if a number is a prime with regex?

Do you know?

If you can solve this problem, with trivial modification, you can check whether a number is part of a twin prime, since isolated prime has opposite definition of a twin prime.

\$\endgroup\$

closed as off-topic by Erik the Outgolfer, Kritixi Lithos, Blue, clismique, Toto Feb 6 '17 at 9:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Erik the Outgolfer, Kritixi Lithos, Blue, clismique, Toto
If this question can be reworded to fit the rules in the help center, please edit the question.

8
\$\begingroup\$

Perl, 54

/^(?!(..+)\1+$)(?=..(?:|(..+)\2+)$)(?=(..(.*))\4\3*$)/

I think this is not possible without the Perl look-ahead expression... Firstly, there is no positive regex to match the prime number. You can only match a non-prime by simulating multiplication: (..+)\1+. To negate it, I use negative look-ahead: /^(?!(..+)\1+$)/ matches prime numbers (neglecting the 0, 1 case).

The beauty of the look-ahead is that it is zero-width, i.e. eats no characters. This means you can actually AND those conditions! My regex is composed of 3 look-aheads, corresponding to AND-ing 3 conditions:

  • (?!(..+)\1+$) - N (length of the string) is the prime number
  • (?=..(?:|(..+)\2+)$) - N-2 is a non-prime - this is a trival modification of the basic non-prime expression - (..+)\1+) - just add two characters. The (?:|...) is included to also match an empty string (case N=2 should match too).
  • (?=(..(.*))\4\3*$) - N+2 is a non-prime - again, trivial modification of the basic non-prime expression - cut two characters out of one repetition.

Test:

$ perl -E'($"x$_)=~/^(?!(..+)\1+$)(?=..(?:|(..+)\2+)$)(?=(..(.*))\4\3*$)/&&say for(2..200)'
2
23
37
47
53
67
79
83
89
97
113
127
131
157
163
167
173
\$\endgroup\$
  • 1
    \$\begingroup\$ Instant accept. Don't think there is any other answer. I kinda expect this to be easy. My solution is the same, except that I also test for 1 in p-2 (you only test for composite and 0), but it doesn't affect the final result. \$\endgroup\$ – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Feb 8 '14 at 5:20
  • \$\begingroup\$ Well, easy... it seemed pretty impossible, until I got the idea to use look-aheads ;-) \$\endgroup\$ – Tomas Feb 8 '14 at 5:29

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