|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #3Ended |
G - Suma de Primos.
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Un número positivo puede ser expresado como la suma de diferentes números primos de varias formas. Dado dos números enteros positivos $N$ y $K$ usted debe contar las maneras de expresar $N$ como la suma de $K$ números primos distintos. Las soluciones $3 + 5$ y $5 + 3$, cuando $N = 8$ y $K = 2$, se deben contar como una sola.
Cuando $N = 24$ y $K = 3$ la respuesta es dos, porque podemos de los conjuntos de primos $\{2, 3, 19\}$ y $\{2, 5, 17\}$ sumar sus elementos y obtener $24$. No hay otros conjuntos de tres primos que sumen $24$. Para $N = 24$ y $K = 2$ la respuesta es tres, $\{5,19\}$, $\{7,17\}$ y $\{11,13\}$. Para $N = 2$ y $K = 1$ la respuesta es uno, el conjunto $\{2\}$. Para $N = 1$ y $K = 1$ la respuesta es cero, ya que se asume que $1$ no es primo. Para $N = 4$ y $K = 2$ la respuesta es $0$.
Cuando $N = 24$ y $K = 3$ la respuesta es dos, porque podemos de los conjuntos de primos $\{2, 3, 19\}$ y $\{2, 5, 17\}$ sumar sus elementos y obtener $24$. No hay otros conjuntos de tres primos que sumen $24$. Para $N = 24$ y $K = 2$ la respuesta es tres, $\{5,19\}$, $\{7,17\}$ y $\{11,13\}$. Para $N = 2$ y $K = 1$ la respuesta es uno, el conjunto $\{2\}$. Para $N = 1$ y $K = 1$ la respuesta es cero, ya que se asume que $1$ no es primo. Para $N = 4$ y $K = 2$ la respuesta es $0$.
Input
La entrada es una secuencia de dos números, $N$ y $K$ separadas por un espacio. $1 \leq N \leq 1120$ y $1 \leq K \leq 14$. La entrada termina cuando se leen dos $0$.
Output
Se debe de imprimir por cada línea la respuesta, debe asumir que esta es menor que $2^{31}$.
Sample test(s)
Input
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
Output
2
3
1
0
0
2
1
0
1
55
200102899
2079324314