def is_prime(n): return not re.match(r'^.?$|^(..+?)\1+$', '1'*n) This works by first converting the number to unary, i.e. 5 will be ‘11111’ and 3 will be ‘111’ and so on. First, it tries to match 0 or 1 in the LHS and then uses backreferences to try and match multiples of 2, 3, 4 and so on until a match is found or string length is exceeded. For a deeper analysis please read: https://iluxonchik.
I’m going to use python. Regex can be used by using the re library. You should not refer to this post as these are just notes, it would be better to follow the actual documentation of the library. To use regex, which uses backslashes \ we must use raw python strings like r"\n". . matches anything but a newline \d matches 0-9 while \D matches anything but digits. Similarly, \w matches word chars.