Продолжаем обсуждать решения задач автором канала: Задача Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-е простое число - 13. Какое число является 10001-м простым числом? Решение Оно здесь довольно лобовое: перебирать натуральные числа, определять простые, пока мы не отыщем 10001-е. Автор так и делает. Единственное, стоит обратить внимание на некоторую оптимизацию функции, определяющей простое число. Она проверяет не все множители числа, а только до квадратного корня из числа, потому что далее они начнут повторяться...

Долго размышляя над созданием эффективного алгоритма факторизации чисел, я наткнулся на довольно интересную проблему - проблему оценки вероятности существования делителя на конкретном промежутке для произвольного натурального числа. Разрешение данного вопроса, на мой взгляд, способно продвинуть создание вероятностного алгоритма разложения числа на простые множители. Формулировка Пусть у нас есть произвольное число из множества натуральных чисел, тогда с какой вероятностью p(x) у числа есть делитель...