print1591. Марсианская простота

printМарсианская простота

Ограничения: время – 2s/4s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
Источник: http://imcs.dvgu.ru/cats/ Весенний турнир, 2011
loading