정규식으로 소수 판별하기

val regex = """^1?$|^(11+?)\1+$""".toRegex()

fun isPrime(num: Int): Boolean {
	return !regex.matches("1".repeat(num))
}

fun main(args: Array<String>) {
	(0..10).forEach {
		if (isPrime(it))
			println("$it is prime")
		else
			println("$it is not prime")
	}
}​

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

위 정규식은 정확히 말하자면 1의 개수가 소수인지 아닌지를 판별해준다.

이게 무슨 뜻인고 하니...

 

자세히 보면 다음의 2가지 로직이 or(|)로 묶여있는 것을 확인할 수 있다.

1. ^1?$
2. ^(11+?)\1+$

1번째 로직은 ?를 사용해서 1이 0개 있을 때와 1개 있을 때를 확인한다.

0과 1은 소수가 아니고, 소수가 아니면 해당 정규식에 매칭된다.

 

2번째 로직은 \1 백 레퍼런스를 사용해서 (11+?)가 반복되는지를 검사한다.

가령 6(=1이 6개, 111111)이 소수인지 확인하기 위해 먼저 11이 반복되는 꼴인지 확인할 것이다. 111111 에서 빨간색 11이 (11+?)에 매칭되고, 이 매칭된 11이 뒤에 2번 반복되는 꼴이므로 ^(11+?)\1+$ 정규식에 매칭된다. 정규식에 매칭됐으므로 소수가 아니다.

 

7은 11이 반복되는 꼴도 아니고, 111이 반복되는 꼴도 아니고, 1111부터는 절반을 넘어가서 \1+가 성립을 안 하니 모두 매칭이 되지 않는다.

정규식에 매칭이 되지 않았으므로 소수이다.