333 : 特殊分割

あらゆる正の整数は、各項がいずれも$2^i \times 3^j$（$i,j \geq 0$）と表されるように分割することができる。

いずれの項も他の任意の項を割り切らないような分割のみを有効(valid)なものと考えよう。 例えば、$17 = 2 + 6 + 9 = (2^1 \times 3^0 + 2^1 \times 3^1 + 2^0 \times 3^2)$という分割は、2 が 6 を割り切るので有効でない。$17 = 16 + 1 = (2^4 \times 3^0 + 2^0 \times 3^0)$という分割も、1 が 16 を割り切るので有効でない。17 の唯一の有効な分割は $8 + 9 = (2^3 \times 3^0 + 2^0 \times 3^2)$である。

多くの整数は１つより多くの有効な分割を持つ。そのような最初の数である 11 は次の２つの分割がある。 $11 = 2 + 9 = (2^1 \times 3^0 + 2^0 \times 3^2)$ $11 = 8 + 3 = (2^3 \times 3^0 + 2^0 \times 3^1)$

$n$ の有効な分割の数を$P(n)$としよう。例えば$P(11)=2$である。

$P(17)$のように、有効な分割が１つのみとなる素数$q$だけを考えよう。

$P(q)=1$となる素数 $q<100$ の和は 233 である。

$P(q)=1$となる素数 $q<1000000$ の和を求めよ。