Strumenti Utente

Strumenti Sito


primepro

Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

Link a questa pagina di confronto

primepro [2017/05/03 15:48] (versione attuale)
Linea 1: Linea 1:
 +http://​www.noulakaz.net/​weblog/​2007/​03/​18/​a-regular-expression-to-check-for-prime-numbers/​
 +
 +<​code>​
 +/​^1?​$|^(11+?​)\1+$/​
 +</​code>​
 +
 +Is 7 prime?
 +
 +To know this, the function first generates “1111111″ (from “1″ * 7) and tries to see if that string does not match /​^1?​$|^(11+?​)\1+$/​. If there is no match, then the number is prime.
 +
 +Notice that the regular expression has two parts (separated with the vertical bar |).
 +
 +The first part is /^1?$/ is trivial and matches with beginning of line (^), an optional 1 (1?)
 +and end of line ($) which implies that it matches either the empty string or “1″.
 +This simply indicates that calling that function with n==0 or n==1 will correctly return false (as the “1″ * n will match with the first part of the regular expression)
 +
 +The second part is where the magic occurs…
 +
 +/​^(11+?​)\1+$/​ matches with beginning of line (^) then by (11+?) then by \1+ and finally by end of line ($).
 +I guess that you know that \1 is a variable which is bound to whatever was matched previously (in our case by (11+?)).
 +
 +Let’s proceed slowly…
 +
 +(11+?) does two things
 +
 +- It matches with “1″ followed by one or more ones minimally. This means that it matches with “11″ initially (notice that if there was no ? (i.e. (11+) was used instead, the whole string would have matched)
 +- The string obtained (“11″ initially) is bound to the variable \1.
 +
 +\1+ then matches with whatever has been matched above (“11″ initially) repeated one or more times. If this match succeeds then the number is not prime.
 +
 +If you are following, you’ll realise that this eliminates all even numbers except 2 (for example, 8 is “11111111″ and therefore (11+?) will match with “11″ and \1+ will match with “111111″).
 +
 +As for odd numbers (in our case 7), the (11+?) matches with “11″ initially but \1+$ cannot be true (notice the $) as there are 5 remaining ones.
 +The regular expression engine will backtrack and will make (11+?) match “111″ and here also \1+$ won’t be true because there will be 4 remaining ones
 +(and \1+$ will only match with a number of ones which is a multiple of 3 followed by end of line) etc. hence “1111111″ will not match the regular expression
 +which implies that 7 will be considered as being prime :-)
  
primepro.txt · Ultima modifica: 2017/05/03 15:48 (modifica esterna)