Prime Numbers Generation

Problem #61

Tags: mathematics arrays

Who solved this?

Back to English version

В этой задаче мы реализуем генератор простых чисел. Простыми называются положительные целые, не имеющие делителей кроме 1 и самого числа. Вы можете прочесть больше в википедии. Самые популярные для начинающих программистов алгоритмы - Решето Эратосфена и Перебор делителей. Вы можете найти подробности о них по этим ключевым словам.

Итак, давайте создадим список или массив простых чисел в порядке возрастания:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...]

И потом напечатаем те из них, которые соответствуют индексам заданным во входных данных.

Входные данные указывают в первой строке количество простых чисел которые нужно напечатать.
Вторая строка содержит интересующие нас индексы в массиве простых чисел. Они будут в диапазоне от 1 до 200000.
Ответ должен содержать простые числа соответствующие указанным позициям в массиве.

Внимание в этой задаче индексы массива начинаются с 1 а не с 0 - это для того чтобы легче было пользоваться (в целях проверки) готовыми списками простых чисел из интернета.

Пример:

входные данные:
4
7 1 199999 4

ответ:
17 2 2750131 7

Постарайтесь реализовать алгоритм эффективно - при правильном подходе все 200000 чисел должны генерироваться за время около секунды (м.б. несколько медленнее на скриптовых языках вроде Python, или на менее современных компьютерах).

You need to login to get test data and submit solution.