Come funziona questa espressione regolare?

Question

Da this article,

/^1?$|^(11+?)\1+$/ controlla se un numero (il suo valore in unario) è primo o meno.

Utilizzando questo, perl -l -e '(1 x $_) !~ /^1?$|^(11+?)\1+$/ && print while ++$_;' restituisce un elenco di numeri primi.

Non ho abbastanza esperienza con Perl, ma quello che ho capito è che l'espressione regolare sarà true per un numero che non è primo. Quindi, se stampiamo tutti i numeri che non producono vero con questa espressione, abbiamo un elenco di numeri primi. Questo è ciò che la query Perl sta cercando di fare.

circa la parte regex,

^1?$ parte è per il conteggio 1 come Not Prime

^(11+?)\1+$ è per abbinare numeri non primi a partire dal 4.

---

Quello che non mi capire è perché è necessario il ? nel regex necessario. Secondo me /^1$|^(11+)\1+$/ dovrebbe essere più che bene ed effettivamente

perl -l -e '(1 x $_) !~ /^1$|^(11+)\1+$/ && print while ++$_;' mi dà la stessa serie di numeri primi.

C'è qualche difetto nella mia comprensione dell'espressione regolare? Perché sono necessari i ? s?

Non è ? supposto che corrisponda a zero o una occorrenza dell'espressione precedente?

Answer 1

Il primo ? corrisponde alla stringa vuota (ad esempio 0) come non principale. Se non ti interessa se regexp corrisponde a 0, non è necessario.

Il secondo ? è solo per efficienza. + è normalmente "avido", il che significa che corrisponde a tutti i caratteri disponibili e quindi retrocede se il resto della regexp non corrisponde. Lo +? lo rende non-goloso, quindi corrisponde solo a 1 carattere, e quindi cerca di trovare più corrispondenze se il resto della regexp non corrisponde. (Vedi the Quantifiers section of perlre per ulteriori informazioni sulla corrispondenza avidi e non avidi.)

In questo particolare regexp, il (11+?) significa che verifica divisibilità per 2 ('11'), quindi 3 ('111'), poi 4, ecc Se si è utilizzato (11+), sarebbe testare divisibilità per N (il numero stesso), quindi N-1, quindi N-2, ecc. Poiché un divisore non deve essere maggiore di N/2, senza lo ? si perde tempo a testare molti "potenziali" divisori che non possono funzionare. Corrisponderebbe comunque ai numeri non primi, solo più lentamente. (Inoltre, $1 sarebbe il divisore più grande invece che il più piccolo.)

Answer 2

Il primo ? farà sì che "" (la stringa vuota, zero unario) non sia un numero primo. Lo zero è definito come non primo.

Il secondo è diverso; blocca l'espressione regolare da corrispondenza avida. Dovrebbe migliorare notevolmente le prestazioni della partita, poiché la prima parte di quella sezione ((11+)) non consumerà quasi l'intera stringa prima di dover tornare indietro. Se ometti il ​​punto interrogativo, stai effettivamente testando se lo n è divisibile per n-1 e così giù; se lo includi, stai verificando la divisibilità di due prima e così via. Ovviamente, i numeri tendono a essere divisibili per fattori più piccoli più spesso, quindi la tua corrispondenza sarà più veloce.