[BOJ #5641] 겉보기에 쌍둥이 소수

BOJ #5641, 겉보기에 쌍둥이 소수 문제입니다.

 

작성시각 기준 푼 사람이 16명밖에 되지 않는 문제입니다만 그렇게 어렵지는 않았습니다. 입력으로 n과 t가 주어지면 n자리 겉보기에 쌍둥이 소수를 '아무거나' 출력하면 됩니다. 그런데 3500 <= n <= 5000입니다. 몇 가지 시도를 해 보면 3500이라는 수가 어떤 의미인지 알 수 있습니다.

 

접근

우선 3500자리에서 5000자리 되는 수를 int형으로 접근하려고 하는 것은 살짝 위험한 생각입니다. 이런 경우 보통은 문자열으로 접근할 생각을 해야 합니다. 결론적으로 저는 int형과 str형을 적절히 조합해서 풀었습니다.

 

겉보기에 소수에 관하여...

에라토스테네스의 체 방식을 이용하면, 쉽게 겉보기에 소수를 만들 수 있겠죠. 그런데 가령 t가 8000이라고 하면 해당 수가 겉보기에 소수인지 판별하기 위해 2 이상 8000 이하의 모든 자연수로 나눠보아야 할까요? 아닙니다. 곰곰이 생각해 보면 8000 이하의 소수로만 나누어 보면 됩니다. 어떤 수가 8000 이하의 모든 소수로 나누어떨어지지 않는다고 하면 2 이상 8000 이하의 모든 자연수로 나누어떨어지지 않습니다. 이 사실은 귀류법으로 간단히 증명할 수 있습니다.

• (결론의 부정) t 이하의 모든 소수로 나누어떨어지지 않는 수가 t 이하의 어떤 합성수로 나누어떨어진다.
• 어떤 합성수는 그보다 작은 소수의 곱으로 나타낼 수 있다.
• (모순) 따라서 해당 수는 합성수의 약수인 소수로 나누어떨어진다.
• (결론) t 이하의 모든 소수로 나누어떨어지지 않는 수는 t 이하의 모든 합성수로 나누어떨어지지 않는다.

따라서 8000 이하의 모든 '소수'로만 나누어보면 됩니다.

 

추가적으로, a < b일 때 모든 t == a일 때의 겉보기에 소수는 t == b일 때의 겉보기에 소수입니다. 이는 정의에 의해서 자명합니다. 따라서 t == 8000일 때의 겉보기에 쌍둥이 소수를 계산해 두면 t의 값과 상관없이 답을 만드는 데 사용할 수 있습니다. 따라서 우리는 t == 8000일 때의 겉보기에 쌍둥이 소수를 구하면, 그리고 이 수를 이용해서 자릿수를 마음대로 확장할 수 있으면, 이 문제를 풀 수 있습니다. t == 8000일 때의 겉보기에 쌍둥이 소수를 구하는 것은 어렵지 않게 할 수 있으시겠죠?

 

자릿수의 확장에 관하여...

혹시 우리가 충분히 구할 수 있는 범위의 겉보기에 소수를 구한 후 그것을 더 큰 자리수로 확장할 수 있을까요? 예를 들면 n == 2, t == 6이라는 조건에서 17을 구했다고 칩시다. 이를 n == 100, t == 6인 수를 구하는 데 이용할 수 있을까요? 아까의 결론에 의해서 우리는 2, 3, 5로 나누어떨어지지 않는 수를 찾으면 됩니다.

 

우선, 일단 자릿수를 하나 확장해 보죠. 간단히 1을 붙여 117을 만들겠습니다. 3으로 나누어떨어지게 되었네요. 이처럼 아무 규칙 없이 자릿수를 확장하면 안 됩니다. 조금만 생각해 보면, 다음을 적용할 수 있습니다.

(A + B) % C == ((A % C) + (B % C)) % C

B를 17이라고 생각하고, A는 확장된 수와 B와의 차이라고 생각해 봅시다. A % C를 0으로 만들면(A가 C로 나누어떨어지게 하면) 다음 식이 성립하겠네요.

(A + B) % C == (B % C) % C == B % C

C는 2, 3, 5가 가능합니다. 가능한 모든 C로 나누어떨어지는 수를 만들어서 그것을 17에 더하면 나머지는 보존되는 것입니다!

 

가능한 모든 C로 나누어떨어지는 수를 만들려면 간단히 그냥 곱하면 됩니다. 2 * 3 * 5 == 30이 되겠네요. 이는 최소공배수이므로 이젠 어떤 수를 곱하더라도(확장하더라도) 계속 가능한 모든 C로 나누어떨어집니다. 그러면 10 ^ 98을 곱하면 되겠네요! 30 * 10 ^ 98 + 17은 모든 조건을 만족합니다!

 

문제로의 적용

8000 이하 모든 소수의 곱은 몇 자리일까요? 이를 계산해 보면 문제의 입력 범위가 왜 이렇게 잡혀 있는지 알 수 있게 됩니다. 이를 계산하고 아까 t의 값과 상관없이 구해 둔 겉보기에 쌍둥이 소수를 이용합시다. 그리고 중간에 0을 자릿수에 맞게 붙여 주기만 하면 되겠네요.