Удачные числа
(Время: 1 сек. Память: 32 Мб Сложность: 82%)
Алексей на уроке математики узнал о новой последовательности «удачных» чисел. Первое удачное число равно 1.Чтобы сгенерировать последующие «удачные» числа, создайте массив возрастающих целых чисел, начиная с 2:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ...
Возьмем первый элемент результирующего массива в качестве следующего «удачного» числа 2. Удалим каждый "2-й" индексированный элемент из массива (включая первый):
3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 ...
Возьмем первый элемент результирующего массива в качестве следующего «удачного» числа 3. Удалим каждый "3-й" индексированный элемент из массива (включая первый):
5 7 11 13 17 19 23 25 29 31 35 ...
Возьмем первый элемент результирующего массива в качестве следующего «удачного» числа 5. Удалим каждый "5-й" индексированный элемент из массива (включая первый):
7 11 13 23 25 29 31 ...
Возьмем первый элемент результирующего массива в качестве следующего «удачного» числа 7. Удалим каждый "7-й" индексированный элемент из массива (включая первый):
11 13 17 23 25 29 ...
В результате получим бесконечный ряд «удачных» чисел:
1 2 3 5 7 11 13 17 23 25 29 37 41 43 47 53 61 67 71 77 83 89 91 97 ...
Ваша задача ответить на Q запросов вида: сколько «удачных» чисел, не превышающих число N ?
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число Q (1 ≤ Q ≤ 100). Во второй строке через пробел Q заданы натуральных чисел Ni (1 ≤ i ≤ Q; 1 ≤ Ni ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на каждый запрос через пробел.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6
1 10 5 3 5 4 | 1 5 4 3 4 3 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
