Как узнать простое число по его номеру

Простое число — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя.

Чтобы проверить является ли какое-то число простым, напрашивается наивный метод решения - проверить делимость его на все натуральные числа от 1 до n (хотя достаточно лишь до квадратного корня из него). Если в какой-то момент остаток от деления даст 0 (то есть число поделилось без остатка), значит оно составное, а в противном случае является простым.

Такой алгоритм прост, но требует довольно много проверок на делимость, из-за чего может быть применён для проверки небольшого числа. А что будет, если применить его для поиска простого числа по заданному номеру n?

Решение кажется очевидным: начнём перебирать подряд числа и проверять их на простоту. Как только обнаружим n простых чисел, остановимся и вернём в результате последнее найденное число. Однако, даже для не очень большого числа n данный метод будет работать чрезвычайно долго, поскольку чем больше будет число, тем дольше будут перебираться его делители.

Вот тут нам на помощь и приходит быстрый алгоритм — решето Эратосфена. Данный алгоритм позволяет найти все простые числа в интервале от 2 до N за довольно короткое время, но нам то нужно найти n-ое простое число, а про индексы в данном алгоритме ничего не сказано. Если бы можно было узнать, в каком интервале находится n-ое простое число, то задача была бы мгновенно решена применением решета. Однако как же решить данную задачу, не зная примерное значение числа?

Как работает решето Эратосфена

Мы предлагаем следующее решение: получим число n и создадим два массива размерности n: primes - массив для хранения будущих простых чисел и numbers - массив для хранения обычных чисел для применения просеивания решетом. Заполним массив numbers числами от 0 до n - 1, а в нулевой элемент массива primes положим 2, поскольку 2 — первое простое число.

Код программы для поиска простого числа по его номеру

#include <iostream>

int main () { 
    int n; 
    
    std::cout << "Enter number of prime number: ";
    std::cin >> n; // считываем номер простого числа, которое нужно найти

    int size = n; // число элементов для массива чисел для просеивания
    int *primes = new int[n]; // массив простых чисел
    int *numbers = new int[size]; // массив для чисел

    for (int i = 0; i < size; i++)
        numbers[i] = i; // заполняем массив (число равно индексу элемента)

    primes[0] = 2; // первое простое число - 2
    int i = 0; // индекс текущего простого числа

    while (i < n) {
        int p = primes[i++]; // запоминаем текущее простое число

        for (int j = p * 2; j < size; j += p)
            numbers[j] = 0; // обнуляем все кратные ему числа в массиве

        while (numbers[p + 1] == 0)
            p++; // ищем следующее ненулевое число

        if (p + 1 >= size) { // если выйдем за границы, расширяем массив
            int *tmp = new int[size * 2];

            for (int k = 0; k < size; k++)
                tmp[k] = numbers[k];

            delete[] numbers;

            size *= 2;
            numbers = tmp;

            for (int j = size / 2; j < size; j++)
                numbers[j] = j; // заполняем новую часть массива числами

            i = 0; // возвращаемся к начальной стадии просеивания
        } else 
            primes[i] = p + 1; // запоминаем новое простое число
    }

    std::cout << n << " prime number is " << primes[n - 1] << std::endl;

    delete[] numbers;
    delete[] primes; 
}

Теперь нам нужно искать числа до тех пор, пока не найдём все n, поэтому обнуляем переменную i, обозначающую текущий индекс простого числа и запускаем цикл пока с условием i < n.

Запоминаем в переменной p текущее простое число (на первой итерации это будет 2), увеличивая текущий индекс простого числа на 1 и просеивая массив чисел от 2p до размера массива чисел (тем элементам массива, где стоят кратные p числа (кроме самого p), проставляем нули, после чего ищем первое ненулевое число — оно и будет следующим простым числом.

В дальнейшем может возникнуть проблема, что n-ое простое число ещё не найдено, а массив чисел уже закончился. Простым решением данной проблемы будет увеличение его размера в два раза и до заполнение числами. Но если так сделать, то в нём останутся числа, кратные тем, что ещё уже были просеяны, и требуется их обработать. Простым решением данной проблемы является запуск алгоритма сначала, а именно обнуление индекса текущего простого числа, благодаря чему все операции просеивания будут проведены повторно, но уже для нового более длинного массива.

Если же изменение массива не требовалось, в массив primes просто записывается найденное простое число (первое ненулевое число в массиве numbers).

Когда же цикл завершён, достаточно просто вывести n - 1 элемент в массиве primes или весь массив, если нужны все простые числа до указанного номера.