На самом деле задача простая не потому, что её лег...

Найти $k$-е простое число при $k$ вплоть до $10^8$ — задача нетривиальная с точки зрения производительности и памяти, однако теоретически осуществимая при аккуратной реализации. Ниже разберём основные идеи и возможный алгоритм (подход «сегментированная решето»), который позволяет решать подобные задачи.

Оценка верхней границы для $k$-го простого

Чтобы «знать», до какого числа нам придётся просеивать, часто используют оценку из теории чисел (следствие из теоремы о распределении простых чисел):

$$p_k < k \left(\ln k + \ln\ln k\right) \quad\text{(для достаточно больших }k\text{).}$$

Например, для $k = 10^8$:

• $\ln(10^8) \approx 18{,}42$,
• $\ln(\ln(10^8)) \approx \ln(18{,}42) \approx 2{,}91$.

Тогда

$$\text{верхняя граница} \approx 10^8 \times (18{,}42 + 2{,}91) \approx 10^8 \times 21{,}33 \approx 2{,}13 \times 10^9.$$

На практике чаще берут чуть с «запасом», например:

$$N \approx k \bigl(\ln k + \ln \ln k\bigr) + \text{небольшая константа}.$$

Основная идея решения: «сегментированное решето»

1. Решето для малых простых

1. Сначала нужно найти все простые числа до $\sqrt{N}$.
   • Пусть $N$ — это найденная верхняя граница (например, около $2{,}1\cdot 10^9$ для $k=10^8$).
   • $\sqrt{2{,}1\cdot 10^9}$ — примерно $46\,000$.
   • Это сделать можно обычным решетом Эратосфена в массиве размера $\sqrt{N}$, что совершенно реально по памяти.
   • Полученный список «малых» простых будем использовать для отметки кратных чисел в более крупных интервалах.

2. Сегментированное просеивание

Идея в том, чтобы не хранить огромный массив размером $N$ (который может доходить до нескольких гигабайт), а обрабатывать «кусками» («сегментами») разумного размера, скажем, по $10^7$ или $5 \times 10^7$ чисел за раз — зависит от памяти и от того, какой объём данных вы можете одновременно обрабатывать.

1. Разбиваем интервал $[2; N]$ на сегменты: $$[L, R], \quad R - L + 1 = \text{размер сегмента (например, } 10^7\text{).}$$
2. Для каждого сегмента:
   • Создаём булев массив (или битовый массив) размера «длина сегмента». Изначально проставляем все как «возможные простые» (true).
   • Перебираем заранее найденные «малые» простые $\le \sqrt{N}$. Для каждого простого $p$ находим в текущем сегменте первое число, кратное $p$ (не меньшее $L$), и «вычеркиваем» в булевом массиве все кратные $p$ до $R$.
   • По окончании вычеркивания всё, что осталось «true», — простые числа в текущем сегменте.
   • Считаем, сколько простых мы уже встретили (в предыдущих сегментах), и сколько нашли в текущем. Если в сумме достигаем $k$, останавливаемся и выводим нужное число.

Таким образом, мы проходим по всем сегментам, пока не дойдём до $k$-го простого.

3. Учёт количества найденных простых

Ведём счётчик найденных простых:

• Пусть $count$ — счётчик простых на данный момент.
• В каждом сегменте после просеивания мы проходим по массиву и для каждого «true» увеличиваем $count$.
• Если $\text{count} = k$ — только что найдена $k$-я простая, значит, надо вывести текущее число и завершить программу.
• Если $\text{count} > k$, значит, мы «перепрыгнули», но реально это значит, что в процессе прохода мы можем точно найти, на каком элементе счётчик стал равен $k$.

Оценка времени и памяти

1. Память.

   • Для хранения простых до $\sqrt{N}$ — несколько десятков тысяч чисел, это сущие мегабайты, что вполне допустимо.
   • Для сегмента размером $10^7$ понадобится $10^7$ булевых значений (или примерно $10^7$ бит при битовом хранении, то есть около 1,25 МБ). Если брать сегмент в $5 \times 10^7$, потребуется около 6–7 МБ.
   • Для онлайн-задач обычно ограничение по памяти порядка сотен мегабайт или нескольких гигабайт, так что аккуратно выбранный размер сегмента впишется в лимиты.

2. Время.

   • Прямое просеивание до $2 \times 10^9$ обычным (несегментированным) решетом Эратосфена потребовало бы огромного массива и миллиарды операций.
   • Сегментированное решето значительно экономит память и даёт возможность обрабатывать данные последовательно. При хорошей оптимизации (быстрые операции, использование битовых масок, эффективный ввод-вывод и т. д.) — задача выполнима на быстром языке (C/C++/Rust) в пределах нескольких десятков секунд.
   • Однако требуется очень аккуратно оптимизировать реализацию: от выбора размера сегмента до способа прохода по массивам.

Небольшой пример кода (C++-набросок)

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

cpp
#include <bits/stdc++.h>
using namespace std;

// Находим простые до sqrtLimit обычным решетом
vector<int> simpleSieve(long long sqrtLimit) {
    long long size = sqrtLimit + 1;
    vector<bool> isPrime(size, true);
    isPrime[0] = isPrime[1] = false;
    for (long long i = 2; i * i <= sqrtLimit; i++) {
        if (isPrime[i]) {
            for (long long j = i * i; j <= sqrtLimit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    vector<int> primes;
    for (int i = 2; i <= sqrtLimit; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long k;
    cin >> k; 
    // Если k=1, просто выведем 2
    if (k == 1) {
        cout << 2 << "\n";
        return 0;
    }

    // Верхняя грубая оценка для k-го простого
    // (можно ещё улучшить или взять с запасом)
    long long N = (long long)(k * (log(k) + log(log(k)))) + 10; 
    // Для малых k сделаем минимум
    N = max(N, 100LL);

    // Найдём "малые" простые до sqrt(N)
    long long limit = (long long) floor(sqrt(N)) + 1;
    vector<int> smallPrimes = simpleSieve(limit);

    // Счётчик всех найденных простых
    long long countPrimes = 0;

    // Сегмент берём, например, по 10^6 элементов (для демонстрации идеи)
    const long long segmentSize = 1000000;
    long long start = 2;
    while (start <= N) {
        long long end = min(start + segmentSize - 1, N);

        // Создаём булев массив под текущий сегмент
        vector<bool> isPrime(end - start + 1, true);

        // Вычеркиваем кратные малым простым из smallPrimes
        for (int p : smallPrimes) {
            // Если p^2 > end, дальше нет смысла
            long long p2 = (long long)p * p;
            if (p2 > end) break;

            // Находим первое число в [start; end], кратное p
            // (не меньше start).
            long long base = (start + p - 1) / p * p;
            if (base < p2) {
                base = p2; 
            }
            // Вычеркиваем кратные p
            for (long long x = base; x <= end; x += p) {
                isPrime[x - start] = false;
            }
        }

        // Теперь в isPrime «true» означают простые
        for (long long i = start; i <= end; i++) {
            if (isPrime[i - start]) {
                countPrimes++;
                if (countPrimes == k) {
                    cout << i << "\n";
                    return 0;
                }
            }
        }

        // Переходим к следующему сегменту
        start += segmentSize;
    }

    // Если дошли сюда, возможно, выбранная N была слишком маленькая
    // (или какие-то другие ограничения). По-хорошему, надо было брать N с запасом.
    cerr << "Не удалось найти " << k << "-е простое в пределах " << N << "\n";
    return 0;
}

Важные замечания

1. Оптимизации:

   • Использовать битовые массивы вместо vector<bool> (в C++ vector<bool> — специальная структура, и иногда удобнее вручную хранить данные в uint64_t, чтобы быстрее обрабатывать).
   • Переиспользовать результаты прошлых сегментов для быстрого перехода.
   • Быстрый ввод-вывод (специализированные функции, буферизация).
   • Уточнить верхнюю границу $N$ (часто берут с хорошим запасом, чтобы точно не выйти за нужное $k$).
   • Тонко подобрать segmentSize, чтобы учитывать лимиты по времени/памяти.

2. Практические пределы:

   • При $k=10^8$ итоговое $k$-е простое будет около $2{,}1\cdot 10^9$. Сегментированное решето по такому диапазону — крайне тяжёлая, но в теории выполнимая задача при высокой оптимизации на C++/Rust и достаточных ресурсах (несколько гигабайт оперативной памяти, быстрое CPU, возможно, расширенные лимиты по времени).

3. Тесты на меньших $k$:

   • Всегда рекомендуется сначала проверять корректность кода на малых значениях $k$ (например, $k=1$ должно вывести 2, $k=2$ должно вывести 3, $k=5$ — 11 и т. д.).
   • Убедиться, что программа правильно останавливается и выводит нужное число.

---

Итого:

• Алгоритмически задача сводится к использованию «сегментированного решета Эратосфена» с аккуратным подсчётом найденных простых.
• Главное — тщательная реализация и серьёзная оптимизация, поскольку $k$ может достигать $10^8$.
• При достаточном «железе» и грамотном коде найти $k$-е простое число для очень большого $k$ возможно, но это уже близко к пределам типовых онлайн-решений.