어젯밤, 을 읽다가 신기한 코드 하나를 발견했다.

$ perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ is prime"'

말 그대로 정규식을 써서 소수를 판별하는 perl one liner 코드다. 오 신기한데?

그래서 아래와 같이 실행해 보았다. 그리고 997 입력 후 엔터.

$ perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ is prime"'
997
997 is prime

997이 소수라는 결과가 출력된다.

997은 평소 내가 외우고 있는 소수 중 하나로, 3자리 소수 중 가장 큰 소수이다.

모든 경우를 검증할 수는 없으니 로직을 확인해 보기로 하였다.

  1. 주어진 숫자를 1진법으로 나타낸다. 예를 들면, 3111로, 101111111111로 나타낸다.
  2. 1진법으로 나타낸 숫자가 빈 문자열(0)이거나 1이면 소수가 아니다.
  3. 1진법으로 나타낸 숫자가 ^(11+?)\1+$와 매치되면 소수가 아니다.

여기서 핵심은 백 레퍼런스를 사용해서 11+ 가 반복되는지를 검사하는 3번이다.

  • ?를 붙여 없음, 11, 111, 1111.. 의 순서로 검사하고 있다. 즉, 2, 3, 4.. 로 나누어지는지를 검사한다.
    • 예를 들어 111111로 표현되는 611이 두 번 이상 반복되는 형태이므로 합성수로 판별된다.
  • 만약 절반에 해당하는 지점을 넘어선다면 \1+$가 불가능하므로 매치되지 않을 것이고, 소수로 판별된다.

사실 따지고 보면 이 정규식은 소수를 판별하는 게 아니라 합성수를 판별해낸다. 물론 합성수가 아니면 소수이니 그게 그거긴 하다.

세상에. 숫자 1만 사용해서 소수를 판별해내는 로직이다. 깔끔하고 우아하다.

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

prime regex