Как разбить отрезок на неравные доли?

Question

[SankaSanka]

Есть Главный Отрезок числовой прямой с координатами min и max.

Его нужно разделить на отрезки(задается кол-во), у каждого отрезка будет начальная координата и конечная.
потом из чисел попавших в отрезки мы будем вычислять п ростые числа. Но это уже другая история. :)

Суть вопроса: нужно поделить Главный Отрезок на куски таким хитрым образом чтобы время вычисления на каждом маленьком куске было одинаковое. А оно зависит от величины чисел которые обрабатываются.

Соответственно каждый следующий кусок должен быть меньше предыдущего. (насколько?)

Существует ли какой-то простой алгоритм или формула как это сделать?
Просто поделить на равные доли я уже смогла. Есть готовый массив координат. Можно как старт взять эти координаты и как-то сместить(?).

Comments

[Сергей Соколов]

каким алгоритмом будете проверять простоту числа?

Answer 1

[Сергей Соколов]

Если проверять простоту числа будете последовательным перебором до sqrt(n), то «сложность» можно считать пропорциональной квадратному корню из N. И нужно найти участки с одинаковой площадью под повёрнутой на 90° параболой над каждым из участков.

Интегралы, производные – вспоминайте )

Поскольку задача дискретная, только целые числа рассматриваются, решение всегда будет не точным – как-то будут отличаться «нагрузки» соседних отрезков. И возможны крайние случаи без решения. Например, когда отрезок от 5 до 6 нужно разбить на 1000 частей )

При проверке числа перебирать достаточно только нечетные (в начале проверив чётность N) и не превышать квадратный корень N.

Интеграл от квадратного корня это 2/3 * sqrt(x^3)
Считаете площадь под графиком от Min до Max.
Бьете эту площадь на N равных кусков. И отсчитываете соответствующие такому делению значения x.