Марсианская простота
Ограничения: время – 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⋅106, 2 ≤ M ≤ 104).
Выходной файл должен содержать единственное целое число – количество M-простых чисел.
Источник: http://imcs.dvgu.ru/cats/ Весенний турнир, 2011