Простые числа по порядку: 2, 3, 5, 7, 11, 13, … По номеру n верните простое число, которое стоит на этом месте. Для небольших n подойдёт проверка чисел по одному, но на больших входных данных гораздо быстрее работает решето на достаточно широком диапазоне.
Реализуйте nth_prime(n).
Входные данные
n: номер в списке простых чисел, начиная с 1.
Выходные данные
Верните n-е простое число. nth_prime(1) равно 2.
Ограничения
1 ≤ n ≤ 100 000
Примеры
Ввод:
n = 6
Ожидаемый вывод:
expected = 13
Ввод:
long long n = 6;
Ожидаемый вывод:
long long expected = 13;
Ввод:
long n = 6;
Ожидаемый вывод:
long expected = 13;
Пояснение
Простые числа начинаются так: 2, 3, 5, 7, 11, 13, значит, шестое из них 13.
Ввод:
n = 1
Ожидаемый вывод:
expected = 2
Ввод:
long long n = 1;
Ожидаемый вывод:
long long expected = 2;
Ввод:
long n = 1;
Ожидаемый вывод:
long expected = 2;
Пояснение
Первое простое число - 2.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Можно считать простые числа по мере нахождения, но проверка каждого числа перебором делителей при больших n работает медленно.
Подсказка 2
100 000-е простое число меньше 1 300 000, так что решета такого размера достаточно.
Подсказка 3
Если решето оказалось слишком маленьким, увеличьте его вдвое и попробуйте снова.
Ожидаемая сложность
время O(m log log m), доп. память O(m), где m - размер решета
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.