eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сума простими числами

Сума простими числами

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Натуральне число може бути подане у вигляді суми різних простих чисел тим або іншим способом. Для двох заданих натуральних чисел n та k ви повинні підрахувати кількість способів виразити n у вигляді суми k різних простих чисел. Тут два способи вважаються однаковими, якщо вони дають в результаті один і той же набір простих чисел. Наприклад, 8 може бути подане як 3 + 5 і 5 + 3, але ці способи не розрізняються.

При заданих n і k, наприклад, 24 і 3 відповідо, відповідь два, тому що є всього дві множини {2, 3, 19} і {2, 5, 17}, суми яких дорівнюють 24. Немає ніяких інших наборів з трьох простих чисел, які в сумі дають 24. Для n = 24 і k = 2 відповідь буде три, тому що є три множини {5, 19}, {7, 17} і {11, 13}. Для n = 2 і k = 1 відповідь один, тому що є лише один набір {2}, сума якого дорівнює 2. Для n = 1 і k = 1 відповідь дорівює нулю. Число 1 не є простим, ви не повинні враховувати {1}. Для n = 4 і k = 2 відповідь дорівнює нулю, тому що немає ніяких наборів з двох різних простих чисел, сума яких дорівнює 4.

Ваша задача написати програму, яка повідомляє кількість таких способів для заданих n і k.

Вхідні дані

Кожний рядок є окремим тестом та містить два натуральні числа n (n1120) та k (k14), розділених пропуском. Останній рядок містить два нуля та не обробляється.

Вихідні дані

Для кожного тесту в окремому рядку вивести кількість способів, якими можна представити число n у вигляді суми k різних простих доданків. Відомо, що усі відповіді завжди менші за 2^31.

Приклад

Вхідні дані #1
24 3
24 2
2 1
1 1
4 2
18 3
17 1
17 3
17 4
100 5
1000 10
1120 14
0 0
Вихідні дані #1
2
3
1
0
0
2
1
0
1
55
200102899
2079324314