Все задачи
Средне Решено: 0 Процент решений: 0%

N-е простое число

Верните n-е простое число, считая число 2 первым.

Чему вы научитесь

  • Получать простые числа по порядку
  • Выбирать размер решета, достаточный для ответа
  • Сравнивать перебор делителей с решетом

Условие

Простые числа по порядку: 2, 3, 5, 7, 11, 13, … По номеру n верните простое число, которое стоит на этом месте. Для небольших n подойдёт проверка чисел по одному, но на больших входных данных гораздо быстрее работает решето на достаточно широком диапазоне.

Реализуйте nth_prime(n).

Входные данные

n: номер в списке простых чисел, начиная с 1.

Выходные данные

Верните n-е простое число. nth_prime(1) равно 2.

Ограничения

1 ≤ n ≤ 100 000

Примеры

Пример 1
Ввод:
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.

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.