ゴールドバッハ予想とは「6 以上のどんな偶数も、2 つの素数 (*1) の和として表わすことができる」というものです。
たとえば、偶数の 12 は 12=5+7 、18 は 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 個です。
(*1) 素数とは、1 または自分自身以外に約数を持たない整数のことである。なお、1 は素数ではない。
(*2) 2007 年 2 月現在、5×1017 までの全ての偶数について成り立つことが確かめられている。(Wikipedia)
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットとして、１つの偶数 n (6 ≤ n ≤ 1000000) が１行に与えられます。
データセットの数は 500 を超えません。
データセット毎に素数の組み合せの数を１行に出力します。
134 4330 34808 98792 0
6 72 274 607