Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача G. Марсианская простота

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Как известно, земные математики называют простым натуральное число, имеющее ровно два делителя — единицу и само число. Марсианские математики вместо этого используют понятие M-простого числа, которое имеет ровно M делителей. Например, число 6 является 4-простым, так как имеет делители 1,2,3,6. Обыкновенные простые числа являются в этой терминологии 2-простыми.

Для данных N и M требуется определить количество M-простых чисел в диапазоне от 2 до N включительно.

Формат входного файла

Входной файл содержит числа N M.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество M-простых чисел.

Ограничения

2N5×106, 2M104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 5
0
2
60 12
1
3
10000 12
1040

0.063s 0.008s 13