Troppo ghiotta per non ripostarla.
^1?$|^(11+?)\1+$ è un'espressione regolare che ci dice se un numero è primo.
O meglio, è un'espressione regolare che matcha con una stringa composta di n caratteri "1" (cioè "111" = 3 , "1111" = 4, "11111" = 5 e così via) se n NON è primo.
Qui trovate l'originale:
http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/
(OK è data marzo 2007 ma era sulle CodeProject Newsletter di oggi :p )
e questa è la reg exp: ^1?$|^(11+?)\1+$
Se una stringa di "1" lunga n NON la matcha, allora n è primo.
Perché?
E' composta da 2 pezzi:
^1?$ e ^(11+?)\1+$
^1?$ matcha 1 o la stringa vuota (perché 1 e 0 non sono primi):
^ è l'inizio riga
1? è "zero o un '1'"
$ è il fine riga
^(11+?)\1+$ è più complicato.
l'amico, di noulakaz.net, secondo me la spiega bene dal lato tecnico e male dal lato concettuale.
E' banale. Se n è divisibile per m con 2 <= m < n allora n non è primo.
Da questa banalità deriva l'idea, che è la seguente: se una sequenza di n "1" è splittabile in 2 o più sequenze di m "1" (con m < n) allora n non è primo.
Ed è proprio questo che il motore fa. Prende la tua stringa (ad esempio 1111111, cioè 7) e prende "11". A sto punto prova a romperla in uno o più pezzi da "11", ma avanza un "1", quindi non matcha. Poi ci prova con "111", poi con "1111" etc, ma non ci riesce mai.
Con 9 funziona: prova con "11" e non riesce, poi prova con "111" e vede che 9, cioè "111111111" contiene "111", cioè 3, esattamente tre volte, senza resto, quindi matcha.
Con 10 troverà "11", con 12 sempre "11", con 14 "11", ..., con 25 troverà "11111" cioè 5. Si ferma al più piccolo "divisore", per così dire.
E così via. Fa scena, ma in sostanza è una banalità :)
Quindi, se per caso vi troverete un domani con una macchinetta che fa solo espressioni regolari e vi servirà calcolare se un numero è primo, saprete come farlo. Yuppie! :D
venerdì 30 luglio 2010
mercoledì 21 luglio 2010
venerdì 2 luglio 2010
Iscriviti a:
Post (Atom)