poj2262

要旨:本題は難しくないが、時間の制限に注意しなければならない。基本的な考え方は必ず両側から中間にスキャンを開始することで、得られる素数の差が最大になることを確保することができる.しかし、それだけでは時間テストには通じない。他の人のコードを参考にして、理論上の時間界は同じであるにもかかわらず、実践の中で速度を高めることができることを発見した。

改善:isprimeというカスタム関数を使ったため、大きな数をテストすると、そのオーバーヘッドが大きい。我々はできるだけ大きな数を減らす検査を行うべきである。3から始まる素数で検査を開始すれば、N-minprimeが素数であるかどうかを検査するだけでよい.両方の素数(minprimeとmaxprime)を同時に検出する場合に注意してください。大まかな費用を分析してみましょう。初期のmin+max>N.を仮定すると、私たちのプログラムはmaxprimeを減らすことを選択します。このとき、減らすたびにisprimeを呼び出して大きな数をチェックします。この時の出費は大きい。もし私たちがminprimeだけを大きくすることを採用したら、注意して、私たちは次のminprimeを計算した後にmaxprimeを検査して、総計算回数は多くないはずです(あるいは同じですか?)しかし、minprimeを計算する回数はmaxprimeより多くなり、オーバーヘッドの低減に成功する.

#include "stdafx.h"
#include "iostream"
using namespace std;
int isprime(int N)
{
    if(N%2 == 0&&N!=2)
        return 0;
    for (int i = 3;i*i <=N;i+=2)
    {
        if(N%i==0)
            return 0;
    }
    return 1;
}

int  main()
{
    int minprime ,maxprime,N;
    while(1)
  {
        cin>>N;
        if(N==0)
        break;
   minprime = 3,maxprime = N - 3;
   maxprime = (maxprime%2==0)?maxprime-1:maxprime;// max , 1 （ ）
   while(minprime<=N/2)
   {
       while(!isprime(minprime))// 
           minprime+=2;
       if(isprime(N-minprime))
       {
           cout<<N<<" = "<<minprime<<" + "<<N-minprime<<endl;
           break;
       }
       minprime +=2;
   }
}
    return 0;
}