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

您永远不需要验证一个数字是否可以除自身以及一个数字是否可以除以一个数字。这是没用的：imp % imp == 0 && imp % 1 == 0

否则，您遇到的问题是因为 pow 在将其与整数进行比较时返回双精度或浮点数。由于舍入误差，比较可能会失败。我建议您实现自己的整数幂运算，以避免任何舍入错误。或者将 i 转换为 double 并使用与一些小的 esylon 容差进行比较。

于 2013-03-11T21:01:22.140 回答