Зажимать на «легко» чисел

Я собирался написать описание, как это сделать в целом, но потом я понял, что код может быть проще, чем объяснять.

Самый важный шаг: точно определите, что вы подразумеваете под «простыми простыми» числами.

Пример № 1: 1, 2, 4, 8, 16, 32, 64, 128, …, 1073741824, …

Это силы двух. Итак, просто ceil(log(x)/log(2.0)) решит это.

Пример № 2: 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, …

Существует смесь двух степеней, и несколько ее кратных. Давайте внимательнее посмотрим.

• Подмножество из них может быть описано как степени десяти.
  • Изменение формулы на ceil(log(x)/log(10.0)) решит это.
• Для каждой степени десяти ее кратные 2.0 а также 5.0 также «простые простые числа».
  • Внутри каждой итерации, после проверки значения степени десяти, также проверьте два коэффициента. Если оно умещается в одном из кратных, это значение может быть возвращено как результат.

Следующий код предназначен только для объяснения концепции. Это неэффективно — эффективная версия должна использовать логарифм, чтобы получить результат за O (1) времени.

#include <iostream>
#include <vector>
#include <limits>
#include <stdexcept>
#include <algorithm>

using namespace std;

double getNiceAxisLength(double value, double baseLength, double step, const std::vector<double>& subSteps)
{
typedef std::vector<double>::const_iterator VecDoubleIter;
if (value < 0.0)
{
throw std::invalid_argument("Error: value must be non-negative. Take absolute value if necessary.");
}
if (baseLength <= 0.0)
{
throw std::invalid_argument("Error: baseLength must be positive.");
}
if (step <= 1.0)
{
throw std::invalid_argument("Error: step must be strictly greater than 1.");
}
for (VecDoubleIter iter = subSteps.begin(); iter != subSteps.end(); ++iter)
{
double subStep = *iter;
if (subStep <= 1.0 || subStep >= step)
{
throw std::invalid_argument("Error: each subStep must be strictly greater than 1, and strictly smaller than step.");
}
}
// make ascending.
std::vector<double> sortedSubSteps(subSteps.begin(), subSteps.end());
std::sort(sortedSubSteps.begin(), sortedSubSteps.end());
if (value <= baseLength)
{
return baseLength;
}
double length = baseLength;
double terminateLength = numeric_limits<double>::max() / step;
while (length < terminateLength)
{
for (VecDoubleIter iter = sortedSubSteps.begin(); iter != sortedSubSteps.end(); ++iter)
{
double subStep = *iter;
if (value <= length * subStep)
{
return (length * subStep);
}
}
double nextLength = length * step;
if (value <= nextLength)
{
return nextLength;
}
length = nextLength;
}
return baseLength;
}

int main()
{
double baseLength = 1.0;
double step = 10.0;
std::vector<double> subSteps;
subSteps.push_back(2.5);
subSteps.push_back(5);
for (int k = 0; k < 1000; k += ((k >> 2) + 1))
{
double value = k;
double result = getNiceAxisLength(value, baseLength, step, subSteps);
cout << "k: " << value << " result: " << result << endl;
}

cout << "Hello world!" << endl;
return 0;
}

k: 0 result: 1
k: 1 result: 1
k: 2 result: 2.5
k: 3 result: 5
k: 4 result: 5
k: 6 result: 10
k: 8 result: 10
k: 11 result: 25
k: 14 result: 25
k: 18 result: 25
k: 23 result: 25
k: 29 result: 50
k: 37 result: 50
k: 47 result: 50
k: 59 result: 100
k: 74 result: 100
k: 93 result: 100
k: 117 result: 250
k: 147 result: 250
k: 184 result: 250
k: 231 result: 250
k: 289 result: 500
k: 362 result: 500
k: 453 result: 500
k: 567 result: 1000
k: 709 result: 1000
k: 887 result: 1000
Hello world!

_{Привет, мир!}