Eventuali duplicati:
How to determine if a number is a prime with regex?In che modo questa espressione regolare trova i numeri primi?
This page sostiene che questa espressione regolare scopre numeri non-prime (e per contro-esempio: numeri primi):
/^1?$|^(11+?)\1+$/
Come funziona questo trova i numeri primi?
Penso che l'articolo lo spieghi piuttosto bene, ma ci proverò anche io.
L'ingresso è nel formato unary. 1 è 1, 2 è 11, 3 è 111, ecc. Zero è una stringa vuota.
La prima parte della regex corrisponde a 0 e 1 come non principale. Il secondo è dove entra la magia.
(11+?) inizia cercando i divisori. Inizia con l'essere definito come 11 o 2. \1 è una variabile che si riferisce a quella partita precedentemente acquisita, quindi \1+ determina se il numero è divisibile per quel divisore. (111111 inizia assegnando la variabile 11, e quindi determina che il restante 1111 è 11 ripetuta, quindi 6 è divisibile per 2.)
Se il numero non è divisibile per due, il motore regex incrementa il divisore. (11+?) diventa 111 e riproviamo. Se in qualsiasi momento la regex corrisponde, il numero ha un divisore che non produce resto, e quindi il numero non può essere primo.
Questo è dannatamente brillante. –
questa risposta è davvero incredibile .. :) – espongha
Mi ci volle un minuto per capire questo è inteso per i numeri in base-1 (unario?)
Diverse persone in this ycombinator discussion spiegano questo abbastanza bene. In realtà quelle spiegazioni sono più succinte di quanto penso di poter ottenere, quindi lo lascio al link.
Questo è ** non ** un dup. È una regexp diversa e una tecnica diversa, e ha risposte migliori, per l'avvio. – bmargulies
@bmargulies: Questo * è * un dupe. La regex è la stessa, date le restrizioni di input su questa domanda e il metodo String.matches di Java corrisponde alla regex sull'intera stringa (quindi^e $ sono impliciti), cosa che apparentemente fa. –
@ Rog: le risposte a monte non sono mai state menzionate. – bmargulies