Calcolo numeri primi con espressione regolare
Too good not to repost.
?$ 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
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
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 è obvious:)
So if by chance you will be tomorrow with a machine that only does regular expressions, and you will need to calculate whether a number is prime, you'll know how to do it. Yuppie! : D
<= m < n allora n non è primo.
< n) allora n non è primo.
0 comments:
Post a Comment