in reply to
Re: To Findout Prime number

in thread To Findout Prime number

`perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/'`

OK so I thought i'd elaborate a little on how this works since the monks from the chatterbox took time to explain it to me :)

So you have a number, say 6, and "write" it as a sequence of 1 ie `(111111)` .

If you write it `(11)(11)(11)` "*you just found that 6 = 3 * 2*", as moritz explained it.

ELISHEVA explains the math behind this :

*if there is a repeating group of the same number of ones, then a factorization is possible and hence the number can't be prime.*

It means that if you can write the number as M groups of K ones, then it factorizes as :

`M * [ Sum(p=1->k) 1 ]` which really is just `M * K`

Which means that our number can be divided by M (or K), and therefore it's not prime. Shmem gives an example: *i.e. for m = 1763, the group found would be 11111111111111111111111111111111111111111 repeated 43 times - not prime*

So how does the regexp implement that ? We can decompose it like this :

`m/
^ # start of line
1? # the number 1, zero or one time
$ # end of line
| # alternation
^ # start of line
( # remember the match in \1
11+? # the number 1, then the number 1 once or more t
+imes, but the less time possible
) #
\1+ # the matched sequence, once or more.
$
/x ;
`

So the real trick is in

`(11+?)`. In a standalone context, it will only match 11. That's because

`+?` means

*"once or more but the minimum number of times"*. On the other hand,

`^(11+?)$` will match a whole sequence of ones from begining to end.

Here `(11+?)` is followed by `\1+$` which means : * itself, once or more, until the end of the line *.

So what happens is that the "minimum number of times" that's contained in `+?` is seen from the `\1+$` that is **after** it in the expression

So when no match occurs, the engine will **go back** to the `(11+?)` and try again.

I understand that's what **backtracking** is. Eventually the regexp engine will try every grouping of ones and fine none.

Since it needs at least two groupings to match (enforced by the `+` in `\1+` ), a prime number will not match.

The only problem is that for some numbers you get a `Complex regular subexpression recursion limit (32766) exceeded ` error.
My guess was that it happens when the engine has to try more than 32766 number of times, ie the first fail appears for a number that needs K>32766. That's not the case though, since prime number 32779 does not yield the error. 65558 does, though. I went on and brutforced it, to find that the error appears first with 65536, which is 2 * 32768, which computes since it needs two groups to match...