В целом можно сразу ускорить, поделив все вероятности на p_max. Равномерное распределение будет сэмплиться за O(1). Беда, если есть один тяжелый элемент под 0.999 и много легких по eps. Такое будет сэмплиться за O(n).
На самом деле можно не гадать и считать с любым коэффициентом отсева. Тут выше уже писали про взаимную простоту. Я только сделаю пару доп. выкладок.
Пусть n = p1 * p2 * ... * pk -- произведение k простых чисел. Будем отсеивать все числа, которые не взаимно просты с n. Очевидно, в таком случае число большее любого простого делителя n -- составное.
Количество взаимно простых чисел считается по формуле Эйлера. Для нас это будет phi(n) = (p1 - 1) * (p2 - 2) * ... * (pk - 1). Т.е. доля тех, что пройдут отсев будет phi(n) / n.
Ну и в целом тогда конкретно выше описанный алгоритм можно немного сократить, просто написав
def isProbablyPrime(x):
return x % 2 != 0 and x % 3 != 0 and x % 5 != 0 and x % 13 != 0.
Судя по исходнику, алгоритм всегда возвращает один ответ для фиксированного числа. Особого вина тогда нет. С таким же успехом можно проверить делимость числа на 2, 3, 5 и 7. На каждые 210 чисел придется доля порядка 22% тех, что не делятся ни на одно из маленьких простых.
Такое требование все равно что на вопрос "Куда едем?" отвечать на Ладе-Калина. Стоило бы понять сначала, как вообще эта функция выглядит. Нарисовали б карту x, y -- координаты, z -- температура. Может все вообще линейно, и картинку приложили.
Еще, я так понимаю, для пары пользователей считается некоторое число d(A, B). Оно является метрикой? d(A, B) + d(B, C) >= d(A, C), d(A, A) = 0? И какие оно принимает значения?
ivanesi: пожалуйста. На самом деле количество точек не важно. Так можно сравнивать любые гладкие кривые. Есть небольшой нюанс про вторую производную и нормаль -- это верно только при естественной параметризации. Но для знака это значения не имеет. Так что можно смело считать детерминант и не заморачиваться.
Кстати да. Если научиться находить центральное кольцо, то можно потом пустить несколько лучей в случайно выбранные стороны и посчитать число переходов границ. Взять из получившегося минимум или медиану, что лучше будет работать.