0

少し前に、ブール関数をコーディングして数値が素数かどうかをチェックする方法に関する質問への回答を得ました: bool function for prime numbers。

このことから、動作するコードは

bool prime(int x)
{
if (x < 2) return false;
for(int i=2; i<= sqrt(x); i++) {
if ((x%i) == 0) return false;
}
return true;
}

ただし、コードを次のように変更すると

bool prime(int x)
{
if (x < 2) return false;
for(int i=2; i<= sqrt(x); i++) {
if ((x%i) != 0) return true;
}
return false;
}

数値が多くの整数に対して素数であるかどうかを正しく判断できません。私は、これら 2 つのコード セグメントは同等であると考えていました。このbool prime関数を で動作させる方法はあります!=か?

ありがとう。

4

2 に答える 2

2

いいえ。数値が素数であるかどうかをテストする場合、素因数が 1 つ見つかったからといって素数ではないことがわかります。

そのため、最初の例で for ループを早期に抜け出して false を返すことができます。

if ((x%i) == 0) return false;

単一の数が因数ではないことがわかったからといって、その数が素数または非素数であるとは証明されないため、その条件で早期に終了することはできません。

于 2012-12-26T12:13:36.160 に答える
1

いいえ、できません。

この元のコードは、要因が見つかった場合に早期に戻る機能を利用しています。変更されたバージョンは、要因を見つけた瞬間に早く戻ります。数が素数ではないことを確認する前に、考えられるすべての要素 (少なくとも平方根未満の要素)をテストする必要があるため、提案した方法を機能させることはできません。

余談ですが、わずかな変更でアルゴリズムの効率がほぼ 2 倍になる可能性があります。2 より大きい偶数をテストする必要がないため、最初に 2 をテストし、次に 3 でループを開始し、2 ずつインクリメントします。

bool prime(int x)
{
  if (x < 2) return false;
  if (x%2 == 0) return x == 2;
  for(int i=3; i<= sqrt(x); i+=2) {
    if ((x%i) == 0) return false;
  }
  return true;
}
于 2012-12-26T12:14:09.297 に答える