学校の ACM の練習問題で、非常にイライラします。
今日は素数を求めるアルゴリズムについて話したいと思いますが、完全にこの問題に関連しています。問題を見た友人はもうアイデアを持っているはずですが、以下の説明を読むとイライラするかもしれません。ほほ、あなたの思考を持って、私についてきてください。
まず、問題を分析しましょう。10000 以下の範囲から、2 つの素数の 2 乗の和と等しい素数を求める必要があります。つまり、K = A^2 + B^2 を満たす必要があります。ここで、A と B は素数であり、K ももちろん素数です。良い解法は、まず 1 つの素数を求め、別の異なる素数を求めることです。なぜ異なる素数を求めるのかというと、もし同じだった場合、K が 2 より大きい場合、K は確実に素数ではなくなるからです。そして、平方して足し合わせ、最後に得られた K が素数でないかを確認します。結果が出るまで待つことになると、正直なところ、N 秒待っても結果が出ないと気づいた時には自分のアルゴリズムを最適化する必要があると感じるでしょう。実際、私も最初はそう思っていましたが、結果は...
さて、私の考えについて話しましょう。数学について少し話しましょう。
(1) (A + B)^2 = A^2 + 2*AB + B^2, "平方和" と "和の平方" の変換公式
(2) 奇偶の法則: 2 つの偶数の和は偶数であり、2 つの偶数の積は偶数である。2 つの奇数の和は偶数であり、2 つの奇数の積は奇数である。奇数と偶数の和は奇数であり、積は偶数である。
(3) ゴールドバッハの予想: 2 より大きい任意の 2 つの素数の和は偶数である。
第 3 の法則は非常に重要です。予想ではありますが、コンピュータ科学では計算可能なデータサイズの範囲では証明可能です。試し割り法ですね。
数学の話はこれくらいにして、アルゴリズムの最適化に戻りましょう。以下の分析を続けてください。
K = A^2 + B^2 => K = (A + B)^2 - 2*AB
A + B は偶数（ゴールドバッハの予想）なので、(A + B)^2 も偶数です。K は素数であり、K が 2 でない場合、K は必ず奇数です。なぜなら、これについては説明しませんが、続けて推論します。
K は奇数であり、(A + B)^2 は偶数です。したがって、2*AB は必ず偶数です。2 をかけると必ず偶数になりますし、偶数に偶数を足すと結果は偶数になりますが、K は素数です。偶数ではありません。なぜでしょうか？それならば、A と B のうち少なくとも 1 つの数が特殊な場合になることが確定しています。例えば、1 と 2 です。
したがって、A = B = 1 の場合、K = 2 となり、条件を満たします。A、B のうち 1 つが 1 の場合、反例を挙げると、A = 1、B = 3 の場合、K = 10 は条件を満たしません。また、奇数の平方は奇数であり、奇数に 1 を足すと必ず偶数になります。偶数には素数が含まれているので、なぜ偶数を考えるのでしょうか？A = B = 2 の場合、K = 8 は条件を満たしません。したがって、A、B は 1 つが 2 であり、もう 1 つが他の素数である場合を考慮します。1 と 2 の場合、K = 5 は条件を満たします。
以上から、K の集合 {2, 5} に加えて、他の素数のうち 1 つが 2 であり、もう 1 つが 1 または 2 以外の素数である場合を考慮します。
したがって、アルゴリズムは以下のように最適化できます。
K = 4 + B^2 これで簡単ですね。
アルゴリズムは次のようになります（疑似言語）：アルゴリズムの計算量は O (N) であり、素数かどうかを判断するアルゴリズムの計算量を加えると、最悪の場合でも O (N^2) です。
先に 2 つの素数を求め、それぞれの平方を求め、それから素数かどうかを判断する方法と比べて、かなりの削減になります。
//isPrime () は数が素数かどうかを判断する関数
int N = 10000
int i;
for i = 3 to sqrt(N)
if isPrime( i^2 + 4)
return(i^2 + 4)
else
i = i + 1