서로 다른 소수인 p와 q로 만들어지는 정수 pqqp는 합성 정수(Hybrid Integer)라 부른다.
예를 들어, 800=2552은 합성 정수이다.
C(n)을 n이하의 합성 정수의 갯수라 정의하자.
C(800)=2이고 C(800800)=10790이다.
C(800800800800)을 구하시오.
--------------------------------------------------------------------------
처음에는 숫자가 너무 커서 다루기 겁이 나서 지나갔던 문제이다. 다른 사람의 접근을 보니 숫자가 너무 크기 때문에 log를 이용하면 해결 가능할 것으로 보였다. 문제에서 요구하는 것은 pqqp가 800800800800 이하인 경우를 묻고 있으므로 다음과 같이 된다. 그리고 양변에 로그를 씌워 다시 정의하면 아래와 같다.
pqqp <= 800800800800
log(pqqp) <= log(800800800800)
log(pq)+log(qp) <= log(800800800800)
q*log(p)+p*log(q) <= 800800*log(800800)
소수는 2부터 시작하므로 800800*log(800800)을 최대값으로 보고 이보다 크게 되는 q*log2+2*log(q)의 q값을 구해 상한선으로 두고 이중 반복문을 운영하면 답을 구할 수 있다. 파이썬의 배열 한계를 넘어갈 것을 걱정했는데, 다행히 천만~2천만 사이의 어딘가에서 최대값을 넘는 것을 확인하고, 정확한 값을 구할 수 있었지만 안전하게 해서 답을 구하기로 했다.
15분쯤 소요되었으니 빠른 것은 아니지만 문제를 해결했다는 것에 만족하기로 했다.