Wyrażenie regularne sprawdzające, czy liczba jest pierwsza

Wyrażenie regularne, które potrafi sprawdzić, czy dana liczba jest pierwsza.

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

Jak to działa?

Aby sprawdzić, czy dana liczba jest pierwsza, zapisuje się ją jako ciąg n jedynek, gdzie n równa się jej samej. Np. 5 reprezentowane jest przez ciąg “11111″.

Wyrażenie składa się z dwóch części oddzielonych “|” (or). Jeśli ciąg zostanie dopasowany, dana liczba nie jest pierwsza; w przeciwnym wypadku – jest.

Pierwsza część (^1?$) dopasowuje początek linii (^), zero lub jedną “1″ (1?) oraz koniec linii.
Zatem dopasuje się do ciągów “” oraz “1″ oznaczających kolejno cyfry 0 oraz 1. Jak wiemy 0 i 1 nie są liczbami pierwszymi.

Druga część wyrażenia (^(11+?)\1+$) jest bardziej skomplikowana. Dopasowuje początek linii (^), następnie jeden znak “1″ oraz jeden lub więcej znaków “1″ (11+?). To co zostało dopasowane, trafia w miejsce (\1) i jest dopasowywane jeden lub więcej razy (zachłannie). Następnie dopasowywany jest koniec linii. Ze względu na (zachłanny) znak “+” w \1+, jeśli nie powiedzie się dopasowanie z maksymalną ilością powtórzeń, nastąpi próba dopasowania z mniejszą ilością powtórzeń. Natomiast ze względu na (niezachłanny) znak “?” w 11+?, jeśli minimalny ciąg nie zostanie dopasowany, następuje próba dopasowania ciągu dłuższego o jeden znak.

Najlepiej obrazuje to przykład. Rozważmy cyfrę 9.

Zatem cyfra 9 nie jest liczbą pierwszą.

Leave a Reply