Regular Expression That Checks If A Number Is Prime

Re:Regular Expression That Checks If A Number Is Prime by Chinjut on Thursday September 08, 2016 @08:21PM (#12458721)

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.

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by jayshua on Thursday September 08, 2016 @09:28PM (#12459044)

What do you mean by "non trivial base?"

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by Chinjut on Thursday September 08, 2016 @10:18PM (#12459251)

Oh, just as opposed to unary. Writing numbers in the ordinary way in any ordinary base, which is to say, bases greater than 1; base 2, base 3, base ten, whatever.

[ Parent | on HN ]

Re:Regular Expression That Checks If A Number Is Prime by jerf on Friday September 09, 2016 @09:05AM (#12461752)

It's worth pointing out that we are talking about representing numbers in unary, though. Or even more directly, plain ol' string length since the RE under discussion doesn't even care what symbols you are using, so "11111" = "abcde" under this RE.

[ Parent | on HN ]