-1

「C++Without Fear：A Beginner's Guide That Makes You Feel Smart」の本の第（2）章：Decisions、Decisionsで、このコードのlinを素数プログラムの一部として見ることができます。

while (i<=sqrt(static_cast<double>(n))

「i」が「2」に初期化され、「n」がユーザーの入力である場合。

「n」自体ではなく「n」の「sqrt」と比較するのはなぜですか。

ありがとう。

4

5 に答える 5

6

> sqrt（n）である非素数の因子は得られないためです（他のより小さな因子はすでに見つかっているはずです）。

それは本当に悪いテストですが、次のように書く方がはるかに良いでしょう：

while (i*i <= n)
于 2011-01-18T16:32:59.593 に答える
3

なぜなら、ある数がそれ自体と1以外の因子を持っている場合、それらの因子の少なくとも1つはその数の平方根よりも小さくなるからです。

于 2011-01-18T16:31:54.183 に答える
0

コードは次のようになります。

i = 2;
while (i <= sqrt(static_cast<double>(n)) {
  if (n % i == 0) is_prime = false;
  i++;
}

したがって、ループは、nが余りなしでiで割り切れるかどうかをチェックしています。明らかに、これをチェックする必要があるのは、 nの平方根まで（およびそれを含む）だけです（その場合n / p = qもそうなのでn / q = p）。

于 2011-01-18T16:37:24.800 に答える
0 
while (i<=sqrt(static_cast<double>(n))

と同等です

while(n >= i*i)

作成者が最初のソリューションを選択する理由は、コードの他の部分に依存する可能性があります。

于 2011-01-18T16:32:42.430 に答える
0

アルゴリズム的には、ターゲットの平方根までの可能な要因をチェックするのが正しいです。

Nが素数である場合とそうでない場合があり、sqrt（N）までの因子（1を含まない）がない場合、Nは素数でなければなりません。sqrt（N）自体がその唯一の素因数である可能性があります（たとえば、3 * 3である9）。

17が素数であるかどうかをテストする場合、sqrt（17）は4のすぐ上にあることがわかります。2、3、および4は17に分割されないため、5が大きいので素数である必要があります。

17/5は5未満であり、因子でもある必要があるため、これは当てはまるはずですが、5未満の因子はないことがわかっています。

もちろん、プログラム的にはコードは最適ではありません。これは、doubleや平方根を使用せず、（i * i <= N）のようなものを使用するためです。

于 2011-01-18T16:42:07.970 に答える