НачалоПодразделы
Другие разделы
Дата и время
22/12/2024 15:52:35
1591. Марсианская простота
Марсианская простота
Простые числа, разложение на множителиОлимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (03G) |
| 06/07/2011 | Лето 2011 - 3 (G) |
| 22/07/2019 | Лето 2019 - 10 (упрощенное) (B) |
Ограничения: время – 2s/4s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Как известно, земные математики называют простым натуральное число,
имеющее ровно два делителя – единицу и само число.
Марсианские математики вместо этого используют понятие `M`-простого числа,
которое имеет ровно `M` делителей.
Например, число 6 является 4-простым, так как имеет делители `1,\ 2,\ 3,\ 6`.
Обыкновенные простые числа являются в этой терминологии 2-простыми.
Для данных `N` и `M` требуется определить
количество `M`-простых чисел в диапазоне от `2` до `N` включительно.
Входной файл содержит числа `N` `M` (`2\ ≤\ N\ ≤\ 5*10^6`, `2\ ≤\ M\ ≤\ 10^4`).
Выходной файл должен содержать единственное целое число – количество `M`-простых чисел.
Пример ввода 1
10 5
Пример вывода 1
0
Пример ввода 2
60 12
Пример вывода 2
1
Пример ввода 3
10000 12
Пример вывода 3
1040
