primepro

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

— |
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)