Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Okay, so I went back to Abigail's talk, and discovered that he Doesn't actually explain completely how it works... I was at the talk, and apparently he talked and pointed, but the things he said weren't on the slide. So, I'll attempt to describe How this regexp matches prime numbers only... no promises I'll get it all correct though.

First, we build a string:

1 x $_
This is a string of 1's as long as the number you're testing. Then we test that against the regexp:
/^1?$|^(11+?)\1+$/
The first half of the alternation just takes care of matching an empty string (the number 0) and a single 1 (the number 1) which are prime. I'll break out the second half for clarity:
/^(11+?)\1+$/
In the parens, we match 2 or more ones in succession, in a non-greedy fashion. That means, it'll first try the regex matching "11" in the parens, and if the rest of the regex fails, it'll backtrack and try "111" in the parens, and so on. (sounds like a for loop...)

After the parens, it looks for at least one more occurance of \1, which is what it just captured inside the parens. So, it's basically matching for an integral number of "11"'s in the string, and if that fails, it backtracks and tries matching an integral number of "111"'s in the string, and so on. Because of the anchors, there is no room for extra 1's at the end of the string. And since it needs to match the string of ones twice (once in the parens, and at least one more time after that), if the regex succeeds, you know that the number is divisible by a smaller integer, and is therefore not prime.

I hope this helps... since it was already described in public at least once, I don't feel bad giving this particular magician's secret away. I'm sorry I don't know who originally wrote the code; I'm not sure if it's Abigail's or not.

Alan


In reply to RE: RE: sieve of erothenes by ferrency
in thread sieve of erothenes by maverick

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others scrutinizing the Monastery: (9)
    As of 2014-07-23 02:36 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      My favorite superfluous repetitious redundant duplicative phrase is:









      Results (131 votes), past polls