Come determinare se un numero è un numero primo con regex?

Ho trovato il seguente esempio di codice per Java su RosettaCode :

public static boolean prime(int n) { return !new String(new char[n]).matches(".?|(..+?)\\1+"); } 
  • Non conosco Java in particolare ma capisco tutti gli aspetti di questo snippet tranne che per la regex stessa
  • Ho una conoscenza base e avanzata di Regex come la trovi nelle funzioni PHP integrate

Come funziona .?|(..+?)\\1+ corrisponde ai numeri primi?

Hai detto di aver capito questa parte, ma solo per sottolineare, la stringa generata ha una lunghezza pari al numero fornito. Quindi la stringa ha tre caratteri se e solo se n == 3 .

 .? 

La prima parte della regex dice “qualsiasi carattere, zero o una volta”. Quindi, in pratica, c’è zero o un carattere – o, per quello che ho detto sopra, n == 0 || n == 1 n == 0 || n == 1 . Se abbiamo la corrispondenza, quindi restituire la negazione di quello. Ciò corrisponde al fatto che zero e uno NON sono primi.

 (..+?)\\1+ 

La seconda parte della regex è un po ‘più complicata, basata su gruppi e backreferences. Un gruppo è qualsiasi cosa tra parentesi, che verrà quindi catturato e memorizzato dal motore regex per un uso successivo. Un backreference è un gruppo abbinato che viene utilizzato in seguito nella stessa espressione regolare.

Il gruppo cattura 1 carattere, quindi 1 o più di qualsiasi carattere. (Il carattere + indica uno o più, ma SOLO del carattere o gruppo precedente. Quindi questo non è “due o quattro o sei caratteri ecc.”, Ma piuttosto “due o tre ecc.” Il +? È come +, ma cerca di abbinare il minor numero ansible di caratteri. + normalmente cerca di inghiottire l’intera stringa se ansible, cosa che in questo caso è ctriggers perché impedisce il funzionamento della parte di riferimento.)

La parte successiva è il backreference: quello stesso set di caratteri (due o più), che appare di nuovo. Detto backreference appare una o più volte.

Così. Il gruppo catturato corrisponde a un numero naturale di caratteri (da 2 in poi) catturati. Detto gruppo appare quindi un numero naturale di volte (anche da 2 in poi). Se c’è una corrispondenza, ciò implica che è ansible trovare un prodotto di due numeri maggiore o uguale a 2 che corrisponde alla stringa di lunghezza n … che significa che hai un n. Composito. Quindi, di nuovo, restituisci la negazione della corrispondenza corretta: n NON è primo.

Se non è ansible trovare una corrispondenza, non è ansible trovare un prodotto di due numeri naturali maggiore o uguale a 2 … e si ha sia una non corrispondenza che una prima, quindi di nuovo il ritorno della negazione del risultato della partita.

lo vedi adesso? È incredibilmente ingannevole (e computazionalmente costoso!) Ma è anche un po ‘semplice allo stesso tempo, una volta capito. 🙂

Posso approfondire se hai altre domande, come su come funziona l’analisi regex. Ma sto cercando di mantenere questa risposta semplice per ora (o semplicemente come può essere).

Spiegherò la parte regex al di fuori del test di primalità: la regex seguente, data una String s che consiste nel ripetere String t , trova t .

  System.out.println( "MamamiaMamamiaMamamia".replaceAll("^(.*)\\1+$", "$1") ); // prints "Mamamia" 

Il modo in cui funziona è che la regex acquisisca (.*) \1 , e poi vede se c’è \1+ segue. L’uso di ^ e $ assicura che una corrispondenza debba essere dell’intera stringa.

Quindi, in un certo senso, ci viene dato String s , che è un “multiplo” di String t , e la regex troverà tale t (il più lungo ansible, dal momento che \1 è avido).

Una volta compreso il motivo per cui questa regex funziona, allora (ignorando il primo sostituto nella regex dell’OP per ora) spiegando come è usato per il test di primalità è semplice.

  • Per testare la primità di n , prima genera una String di lunghezza n (riempita con lo stesso char )
  • La regex cattura una String di una certa lunghezza (ad esempio k ) in \1 e prova ad abbinare \1+ al resto della String
    • Se c’è una corrispondenza, allora n è un multiplo corretto di k , e quindi n non è primo.
    • Se non c’è corrispondenza, allora non esiste k tale che divide n , e n è quindi un numero primo

Come .?|(..+?)\1+ corrispondono ai numeri primi?

In realtà, non è così! Corrisponde a String cui lunghezza NON è primo!

  • .? : La prima parte dell’alternanza corrisponde a String of length 0 o 1 (NOT prime by definition)
  • (..+?)\1+ : La seconda parte dell’alternanza, una variazione della regex spiegata sopra, corrisponde alla String di lunghezza n che è “un multiplo” di una String di lunghezza k >= 2 (cioè n è una composito, NON un primo).
    • Si noti che il modificatore riluttante ? in realtà non è necessario per la correttezza, ma può aiutare a velocizzare il processo provando prima k più piccoli

Nota il ! operatore di complemento boolean nell’istruzione return : nega le matches . È quando la regex NON corrisponde, n è primo! È una logica doppio-negativa, quindi non c’è da stupirsi che sia un po ‘confusionario !!


Semplificazione

Ecco una semplice riscrittura del codice per renderlo più leggibile:

 public static boolean isPrime(int n) { String lengthN = new String(new char[n]); boolean isNotPrimeN = lengthN.matches(".?|(..+?)\\1+"); return !isNotPrimeN; } 

Quanto sopra è essenzialmente lo stesso del codice Java originale, ma suddiviso in più istruzioni con assegnazioni a variabili locali per rendere la logica più facile da capire.

Possiamo anche semplificare la regex, usando la ripetizione finita, come segue:

 boolean isNotPrimeN = lengthN.matches(".{0,1}|(.{2,})\\1+"); 

Ancora una volta, data una String di lunghezza n , riempita con lo stesso char ,

  • .{0,1} verifica se n = 0,1 , NON primo
  • (.{2,})\1+ verifica se n è un multiplo corretto di k >= 2 , NON primo

Ad eccezione del modificatore riluttante ? su \1 (omesso per chiarezza), la regex precedente è identica all’originale.


Più divertente regex

La regex seguente utilizza una tecnica simile; dovrebbe essere educativo:

 System.out.println( "OhMyGod=MyMyMyOhGodOhGodOhGod" .replaceAll("^(.+)(.+)(.+)=(\\1|\\2|\\3)+$", "$1! $2! $3!") ); // prints "Oh! My! God!" 

Guarda anche

  • Espressioni regolari: chi è più avido

Trucco regolare regex (anche se molto inefficiente) … 🙂

La regex definisce non-primi come segue:

N non è primo se e solo se N < = 1 OR N è divisibile per alcuni K> 1.

Invece di passare la semplice rappresentazione digitale di N al motore regex, viene alimentato con una sequenza di lunghezza N, composta da un carattere ripetitivo. La prima parte della disgiunzione controlla N = 0 o N = 1 e la seconda ricerca un divisore K> 1, utilizzando le sottorapporti. Costringe il motore regex a trovare una sotto-sequenza non vuota che può essere ripetuta almeno due volte per formare la sequenza. Se tale sottosequenza esiste, significa che la sua lunghezza divide N, quindi N non è primo.

 /^1?$|^(11+?)\1+$/ 

Applica ai numeri dopo la conversione alla base 1 (1 = 1, 2 = 11, 3 = 111, …). I non-primi corrisponderanno a questo. Se non corrisponde, è primo.

Spiegazione qui .