정규식으로 소수 찾기

보통 소수를 찾는 방법이라 하면, 에라토네스의 체(Sieve of Eratosthenes)가 떠오를 것이다.
하지만, 정규식을 이용해 단 몇 줄만으로 소수를 찾는 방법이 있다.

코드는 아래와 같다.

const isPrime = x => (!(/^,?$|^(,,+?)\1+$/.test(Array(++x))));

isPrime(2); // true
isPrime(4); // false
isPrime(19); // true

isPrime함수는 양의 정수 x를 인자로 받고, x에 1 을 더한 크기의 배열을 만든다.
여기서, RegExp.prototype.test는 스트링을 인자로 받기 때문에 Array(++x)는 x개의 ,로 이루어진 문자열로 형변환된다.

즉, x만큼의 ,가 만들어진다.

그리고, /^,?$/와 /^(,,+?)/는 x개의 , 로 이루어진 문자열에 대해 정규표현식 검색을 수행한다.

먼저, 미리 알아두면 좋은 표현식 몇 가지를 설명하고 예시를 들어 코드를 설명하겠다.

정규표현식에서

• ^X는 X로 시작하는 문자열이며, X$는 X로 끝나는 문자열이다.
• (X)?는 X 또는 없음을 뜻한다.
• (X)+는 X가 1번 이상 반복되는 문자열이다.
• (X)\1는 정규식 안 1번째 괄호의 최근 일치 부분에 대한 역참조이다.

만약 x가 5라고 하자. 그럼, RegExp.prototype.test의 인자는 ,,,,가 된다.
(,,+?)는 ,,,,, 의 첫 두 ,,와 매칭된다. 그리고, 역참조 \1은 ,, 이 되며, 전체 정규식은 /^,,(,,)+$/ 이 된다.

,,,,,은 /^,,(,,)+$/ 와 매칭되지 않는다. (,,+?)에서 +? 이 사용되었기 때문에 ,,, 와 매칭을 한다.

(,,+?)는 ,,,,, 의 첫 세 ,,, 와 매칭되며, \1는 ,,, 이 되어 정규식은 /^,,,(,,,)+$/이 된다.

매칭은 또 실패하며, ,,,,와 ,,,,,도 마찬가지이다.
따라서 5는 소수라는 것을 알 수 있다.

이 정규식은 1998 년 Abigail 에 의해 처음으로 구현되었다.