Checking if a number is prime using Regex

12 Jan 2017 - 1 minute read
categories: notes tags: python regex

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:


See Also