Продолжаем обсуждать решения задач автором канала:
Задача
Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-е простое число - 13.
Какое число является 10001-м простым числом?
Решение
Оно здесь довольно лобовое: перебирать натуральные числа, определять простые, пока мы не отыщем 10001-е.
Автор так и делает. Единственное, стоит обратить внимание на некоторую оптимизацию функции, определяющей простое число. Она проверяет не все множители числа, а только до квадратного корня из числа, потому что далее они начнут повторяться.
Решето Эратосфена
Я хочу предложить решение вообще без проверки множителей, которое называется "Решето Эратосфена".
Когда мы двигаемся по натуральному ряду чисел и нашли очередное простое число, то в этот момент настоящего времени мы уже знаем, что в будущем встретим числа, которые кратны этому числу. Например, если мы нашли простое число 2, то знаем, что дальше найдём числа 4, 6, 8 и т.д., которые заведомо не будут простыми, поэтому проверять их не надо.
Но это произойдёт в будущем, где у нас не будет такой контекстной информации.
Поэтому что мы делаем? Мы заранее создаём будущее в виде большого массива чисел. Искать там первое простое число не надо – просто начинаем с числа 2. И мы меняем будущее: проходим дальше до конца массива и помечаем как непростые все числа, кратные 2. Когда мы встретим эти числа в будущем, их уже не нужно будет проверять. Пометка – более дешёвая операция, чем проверка на множители.
Следующее непомеченное число после 2 будет простым. Это 3. С ним мы поступаем так же – помечаем в будущем все числа, кратные 3. Следующее после 3 окажется помеченным, так как было кратно двум. Следующее 5 будет непомеченным, и значит простым. Пометим все числа, кратные 5, и т.д.
Замечу, что надо хранить не массив натуральных чисел, а массив просто признаков "да/нет", потому что само число это индекс массива. На один элемент массива хватит типа char, да и то с избытком.
Как видно из кода, пометка кратных чисел начинается не с ближайшего кратного, а с квадрата простого числа. Эта удобная оптимизация происходит потому, что все числа до квадрата уже заведомо помечены за счёт предыдущих чисел. Чтобы это понять, достаточно на бумажке попробовать вручную заполнить массив для чисел 2, 3 и 5.
Ссылка на онлайн-компилятор языка C с текстом программы:
Расход памяти
У этого алгоритма есть недостаток. Нужно тратить память на хранение чисел. И это довольно значительный объём. Для нахождения 10001-го простого числа нужен массив хранения из примерно 110 килобайт. В данном случае он создаётся на стеке функции main(), которого может и не хватить. Но это не принципиально, так как можно выделить память через malloc().
Принципиально другое – в некоторых реализациях может потребоваться не занимать память совсем, или занимать её очень ограниченно.
Мы можем осуществить ещё две оптимизации: проверять только нечётные числа (потому что чётные, кроме 2, по определению непростые), и также хранить метки побитно, не тратя один байт на одну метку. Так можно сократить потребление памяти в 16 раз, но проблема остаётся. Ведь всегда может потребоваться ещё больше памяти.
Отсюда вытекает ещё одна проблема – сколько памяти надо выделять. Ведь это надо сделать заранее. Скажем, для нахождения 1001-го числа нужно около 8 килобайт, а для 10001-го нужно около 110 килобайт. Здесь есть определённая зависимость, но это отдельная задача, и кажется решается она только приближённо.
Я планирую модифицировать алгоритм Решета Эратосфена, чтобы он использовал фиксированный и небольшой объём памяти для любого количества простых чисел. Возможно, это и не получится, так как я пока не до конца продумал и не проверял. Но напишу про это потом.
Вся подборка задач: