0

この C++ コードに問題があります。整数numは素数かどうかを調べたい数値です。ただし、このプログラムは常に false を返します。おそらく単純なものですが、何も見つかりません。

for(int i=2;i<num;i++){ //primes are allowed to be divided by 1 so we start at 2
        if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
            return false;
        } else if(i == num){ //if we've already done checks as high as possible and not tripped out yet then report success
            return true;
        }
}
4

6 に答える 6

7

i == numあなたのループ条件は であるため、決して発生しませんi<num。試す：

for(int i=2;i<num;i++){ //primes are allowed to be divided by 1 so we start at 2
    if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
        return false;
    } else if(i == num-1){ //if we've already done checks as high as possible and not tripped out yet then report success
        return true;
    }
}

以下に指摘するように、ここでの条件は冗長であり、残りの要素は既にチェックされているため、else2 から - までをチェックするだけで済みます。sqrt(num)

問題をどの程度複雑にするかに応じて、さらに多くの改善を行うことができます。実際のほとんどの方法では、確率的アルゴリズムが使用されます。

于 2012-08-01T06:42:24.480 に答える
4

多くの数字は簡単に除外できるため、すべての数字をチェックする必要はありません。たとえば、numが で割り切れないことを確認した後2、他のすべての偶数をスキップできます。これにより、テストの半分を節約できます。

また、他の因数は より小さくなければならないことも確実にわかっていますnum/2(または実際sqrt(num)には ですが、それは計算が困難です)。その知識により、テストの残りの半分を節約できます。

これで、次のようになりました。

if (num % 2 == 0)
    return false;

for(int i = 3; i < num / 2; i += 2){ 
     if(num % i == 0){ //can be divided by a number other than itself or 1 so we trip out
         return false;
     }
}

// arriving here we have found no factors, so it must be a prime
return true;
于 2012-08-01T07:31:42.500 に答える
1 
bool CheckPrime(int num) {
    bool yayornay = true;
    for(int i = 2; i < num; i++) {
         if(num % i == 0) {
             yayornay = false;
             break;
         }
    }
    return yayornay;
}
于 2012-08-01T07:57:13.597 に答える
1

Will Ness のコードの小さな最適化です。for の外で数値の sqrt を計算するだけです。条件チェックは何度も実行されるため、毎回 sqrt を計算する意味がありません。

if( num == 2 ) return true;
if( num < 2 || num % 2 == 0 ) return false;
int sqrt = sqrt(num);

for( int i=3; i<=sqrt; i+=2 ){   
        if(num % i == 0){ 
            return false;
        } 
}
return true;

これまでのところ、これが最も効率的な方法だと思います。

于 2012-08-01T11:38:43.393 に答える
0 
bool isprime(int n)
{
    if(n<2) return false;
    if(n==2)return true;
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0) return false;
    return true;
}
于 2014-10-25T13:38:44.947 に答える
0

あなたが意図したことを書く適切な方法は次のとおりです。

int i=2;                     // move declaration out
for(/*int i=2*/;i<num;i++){ 
        if(num % i == 0){ 
            return false;
        } // else            // and the final test too
}
if(i == num){                
    return true;
}

しかし、それは効率的ではありません。iがを超えていないことを確認するだけですsqrt(num)。さらに、 をチェックするnum%2と、他の偶数をチェックする必要がなくなるため、増分 2 を使用できます。または、6でカウントすることもできます。

if( num == 2 || num == 3 ) return true;
if( num < 2 || num % 2 == 0 || num % 3 == 0 ) return false;
for( int i=5, j=7, lim=sqrt(num); i<=lim; i+=6, j+=6 ){   
        if( num % i == 0 || num % j == 0 ){ 
            return false;
        } 
}
return true;

（注意：これは、この回答の初期バージョンの「最適化」であると言う別の回答よりも効率的です）。

于 2012-08-01T11:26:38.540 に答える