問題
ゴールドバッハ予想とは「6以上のどんな偶数も、2つの素数※1の和として表わすことができる」 というものです。
たとえば、偶数の12や18は
12=5+7, 18=5+13=7+11
などと表せます。
和が134となる2つの素数の組み合せをすべて書き出すと、以下の通りとなります。
134 =3+131 =7+127 =31+103 =37+97 =61+73 =67+67
=131+3 =127+7 =103+31 =97+37 =73+61
与えられた数が大きくなると、いくらでも素数の組み合せが見つかるような気がします。しかし、 現代数学をもってしてもこの予想を証明することも、反例を作ることもできません※2。ちょっと不 思議な感じがしますね。
そこで、ゴールドバッハ予想を鑑賞するために、偶数 n を入力とし、和がnとなる2つの素数の組 み合せの数を求めるプログラムを作成してください。
和がnとなる素数の組み合せの数とは n = p+q かつ p ≦ q であるような正の素数 p、q の組み合 せの数です。上の例からわかるように和が 134 となる素数の組み合せは6個です。ただし、n は 6 以上 1000,000 以下の偶数とします。
※1 素数とは、1または自分自身以外に約数を持たない整数のことである。なお、1は素数ではない。 ※2 2007年2月現在、5×1017 までの全ての偶数について成り立つことが確かめられている。(Wikipedia)
入力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されま す。 各データセットは以下のとおりです。
1行目 偶数 n
出力
入力データセット毎に素数の組み合せの数を出力します。
入出力例
入力例
134 4330 34808 98792 0
出力例
6 72 274 607