모든 양의 정수는 각 항이 2ⁱx3^j (i,j ≥ 0)인 형태로 분할할 수 있습니다.

어떠한 항도 다른 항으로 나뉘지 않는 분할을 유효하다고 합시다.
예를 들어, 다음 분할 17 = 2 + 6 + 9 = (2¹x3⁰ + 2¹x3¹ + 2⁰x3²)은 6이 2로 나뉘기 때문에 유효하지 않습니다. 또 다른 분할 17 = 16 + 1 = (2⁴x3⁰ + 2⁰x3⁰)도 마찬가지로 16이 1로 나뉘기 때문에 유효하지 않습니다. 17의 분할 중 유효한 것은 8 + 9 = (2³x3⁰ + 2⁰x3²) 하나 뿐입니다.

많은 정수의 유효한 분할이 복수개고, 그 첫 정수는 11로 다음 두 개의 분할이 유효합니다.
11 = 2 + 9 = (2¹x3⁰ + 2⁰x3²)
11 = 8 + 3 = (2³x3⁰ + 2⁰x3¹)

P(n)를 정수 n의 유효한 분할의 수로 정의합니다. 예를 들어, P(11) = 2 입니다.

P(17)처럼 단 하나의 유효한 분할을 가지는 소수 q를 생각해 봅시다.

P(q)=1인 소수 q <100의 합은 233입니다.

P(q)=1인 소수 q <1000000의 합을 구하세요.