You are currently browsing the Philipp Meier's weblog posts tagged: math


partner
forum

This must be shared: /^1?$|^(11+?)\1+$/ to check for prime numbers

That’s all and checks if a string does not consist of a prime number of “1“, e.g. “111” is prime whereas “1111” is not:

[source:ruby]
/^1?$|^(11+?)\1+$/
[/source]

Although this seems cryptic its rather straight forward: match on either “” or “1” (first part until “|“) or match on a substring of 2 or more “1” with repeatedly fits the whole. For the string “111111” the substring “11” fits in 3 times.

Over all its a very high level description of a primality test. I never considered regular expressions as a mathematical domain language.

More details on Avinash Meetoo’s Blog.

blog

Bear
e-mail