Я работал над личным проектом, в котором мне нужно было определить все главные силы между 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);
}
Теперь, если я вызову мою версию _pow () вместо pow () из math.h, вывод отобразится как исключение. Моя реализация неверна? Если нет, pow () из math.h не может работать правильно.
Есть идеи, что вызывает это?
Проблема в том, что 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
).
Вам никогда не нужно проверять, что число делится само по себе и что число делит число. Это бесполезно imp % imp == 0 && imp % 1 == 0
В противном случае ваша проблема в том, что pow возвращает double или float, а вы сравниваете его с целым числом. Сопоставление может быть неудачным из-за ошибки округления. Я бы посоветовал вам реализовать свою собственную операцию целочисленного питания, чтобы избежать ошибок округления. Также можно конвертировать i в double и использовать сравнение с небольшим допуском на эпсилон.