Постулат Бертрана
Постулат Бертрана — это теорема, утверждающая, что для любого целого числа
n > 1 существует хотя бы одно простое число p, удовлетворя неравенству n < p < 2n.Перед вами стоит более сложная задача. Нужно, получив число
n, отвечать на вопросы о том, сколько простых чисел p лежит в диапазоне от n до 2n (то есть при n < p < 2n).Входные данные
Первая строка входных данных содержит целое число
t (1 ≤ t ≤ 100) — количество тестов.В следующих
t строках даётся по одному целому числу n (2 ≤ n ≤ 500 000).Выходные данные
Для каждого теста нужно вывести количество простых чисел в диапазоне от
n до 2n на отдельной строке.Примеры
Вход | Выход |
2
2
239 | 1
39 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB