소수를 판별하는 정규식
1진법을 사용해 소수를 판별하자!
perl regex
어젯밤, 책을 읽다가 신기한 코드 하나를 발견했다.
$ 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진법으로 나타낸다. 예를 들면,
3은111로,10은1111111111로 나타낸다. - 1진법으로 나타낸 숫자가 빈 문자열(
0)이거나1이면 소수가 아니다. - 1진법으로 나타낸 숫자가
^(11+?)\1+$와 매치되면 소수가 아니다.
여기서 핵심은 백 레퍼런스를 사용해서 11+ 가 반복되는지를 검사하는 3번이다.
?를 붙여 없음,11,111,1111.. 의 순서로 검사하고 있다. 즉, 2, 3, 4.. 로 나누어지는지를 검사한다.- 예를 들어
111111로 표현되는6은11이 두 번 이상 반복되는 형태이므로 합성수로 판별된다.
- 예를 들어
- 만약 절반에 해당하는 지점을 넘어선다면
\1+$가 불가능하므로 매치되지 않을 것이고, 소수로 판별된다.
사실 따지고 보면 이 정규식은 소수를 판별하는 게 아니라 합성수를 판별해낸다. 물론 합성수가 아니면 소수이니 그게 그거긴 하다.
세상에. 숫자 1만 사용해서 소수를 판별해내는 로직이다. 깔끔하고 우아하다.
/^1?$|^(11+?)\1+$/