1

私は、0から999までのすべての素数冪を決定する必要がある個人的なプロジェクトに取り組んでいました。私は数学が特に得意ではないため、次のハムフィストブルートフォースアプローチに疲れました。 

bool constexpr is_prime(int imp)
{
    return imp == 1 ? false : (imp % imp == 0 && imp % 1 == 0 && [&imp]{ for(int i = 2; i < imp; ++i)  if(imp % i == 0) return false; return true;}());
}

bool is_prime_power(int imp)
{
    for(int i = 1; i < 1000; ++i)
        if (is_prime(i))
            for (int j = 0; j < 100; ++j)
                if (imp == pow(i, j))
                    return true;
    return false;
}

0 ... 30の場合、出力は次のようになります（A000961による）：

1 2 3 4 5 7 8 9 11 13 16 17 19

しかし、これは私が代わりに得るものです：

1 2 3 4 5 7 8 9 11 16 19

13と17はどこに消えましたか？

私のアプローチでは論理的な問題を見つけることができなかったので、私は自分のpow（）関数を実装しました。

double constexpr _pow(double base, double exp)
{
    return exp == 0 ? 1 : base*pow(base, exp - 1);
}

ここで、math.hからpow（）の代わりに自分のバージョンの_pow（）を呼び出すと、出力は例外として表示されます。私の実装は間違っていますか？そうでない場合、math.hのpow（）は正しく機能しません。何がこれを引き起こしているのか考えていますか？

4

2 に答える 2

3

問題は、double（および一般に浮動小数点数）が正確ではなく、標準ライブラリの数学関数も近似式を使用して計算を行うことです。たとえば、を呼び出すとpow(2, 10)、が取得される場合があります1023.999375（これは、コンテキストに応じて、に切り捨てられる場合があります1023）。

したがって、標準ライブラリの浮動小数点pow()関数を使用する代わりに、整数の独自の正確な実装を使用できます。

int constexpr _pow(int base, int exp)
{
    return exp == 0 ? 1 : base * _pow(base, exp - 1);
}

unsigned（または、必要に応じて、必要に応じて整数型に変更しますlong long）。

于 2013-03-11T21:00:59.617 に答える
1

数がそれ自体を分割し、1つが数を分割することを確認する必要はありません。これは役に立たない：imp % imp == 0 && imp % 1 == 0

そうでなければ、あなたが抱えている問題は、整数と比較している間、powがdoubleまたはfloatを返すためです。丸め誤差が原因で比較が失敗する場合があります。丸め誤差を回避するために、独自の整数累乗演算を実装することをお勧めします。または、iをdoubleに変換し、いくつかの小さなエプシロン許容値との比較を使用します。

于 2013-03-11T21:01:22.140 に答える