НачалоПодразделы
Другие разделы
Дата и время
09/04/2025 23:30:42
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-простыми.
Для данных 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
