Regular Expression That Checks If A Number Is Prime
iluxonchik.github.io
Regular Expression That Checks If A Number Is Prime
1–10 of 117 posts
Re: Regular Expression That Checks If A Number Is Prime
#2Very interesting. Thanks for writing this up.
This is a bit more Perlish (not that I'm an authority):
sub is_prime {
(1x$_[0]) !~ /^(?:.?|(.{2,}?)\1+)$/;
}
Re: Regular Expression That Checks If A Number Is Prime
#3It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405
Because of back references PCRE regular expressions can match non-regular languages as well.
Re: Regular Expression That Checks If A Number Is Prime
#4I wish they'd stop calling these expressions "regular".
Re: Regular Expression That Checks If A Number Is Prime
#5> How would we go about that? Well, all we have to do is add ? in front of the +. This will lead us to the regex.
I was very confused until I realized the author's definition of 'in front' wasn't the same as mine...
Re: Regular Expression That Checks If A Number Is Prime
#6tl;dr if you know a little regex
- convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111)
- handle 0 / 1 separately
- ^(..+?)\1+$
- trick; the WHOLE thing has to match to return (^$)
- first \1 match is "11", ergo string must be "11", "1111", "111111" to match
- second \1 match "111", ergo string must be "111", "111111", "111111111" to match
- and so on. if you find before length of string, it was not prime.
Re: Regular Expression That Checks If A Number Is Prime
#7tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$ - trick; the WHOLE thing has to match to return (^$) - first \1 match is "11", ergo string must be "11", "1111", "111111" to match - second \1 match "111", ergo string must be "111", "111111", "111111111" to match - and so on. if you find before length of string, it was no…
Doesn't this have some relation to https://en.wikipedia.org/wiki/Church_encoding
Re: Regular Expression That Checks If A Number Is Prime
#8It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.
That's true, but it is actually possible to construct true regular expressions that check if a binary string of digits is divisible by an arbitrary integer. Obviously not the quickest or most intuitive way to do it, though.
There's an interesting book that covers some unusual aspects of automata and regular expressions: https://www.amazon.com/Finite-Automata-Regular-Expressions-S...
Re: Regular Expression That Checks If A Number Is Prime
#9tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$ - trick; the WHOLE thing has to match to return (^$) - first \1 match is "11", ergo string must be "11", "1111", "111111" to match - second \1 match "111", ergo string must be "111", "111111", "111111111" to match - and so on. if you find before length of string, it was no…
In other words, it's the Sieve of Eratosthenes implemented via regex: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Re: Regular Expression That Checks If A Number Is Prime
#10It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.
That's true, but it is actually possible to construct true regular expressions that check if a binary string of digits is divisible by an arbitrary integer. Obviously not the quickest or most intuitive way to do it, though. There's an interesting book that covers some unusual aspects of automata and regular expressions: https://www.amazon.com/Finite-Automata-Regular-Expressions-S...
Sure, for a fixed arbitrary integer M. (Supposing the input is fed in in big-endian order, you just keep track of the remainder modulo M as each new bit comes in, updating it by turning r into (r * 2 + new bit) mod M. Since this only requires finite state, it is regular).
But that won't get you a primality checker. You can't get a primality checker. Primes don't comprise a regular language, neither in unary nor in any nontrivial base.