Cardinal

Fie $n$ și $p$ două numere naturale.

Notăm cu $A(n,p)$ mulțimea tuturor numerelor naturale cu proprietățile :

• sunt mai mari sau egale cu $2$ și mai mici sau egale cu $n$;
• descompunerea lor în factori primi conține doar exponenți mai mici sau egali cu $p$.

Exemple :

$A(15,1)$ = $\set{2,3,5,6,7,10,11,13,14,15}$

$A(27,2)$ = $\set{2,3,4,5,6,7,9,10,11,12,13,14,15,17,18,19,20,21,22,23,25,26}$

Cerinţă

Să se scrie un program care citește două numere naturale $n$ și $p$ și determină cardinalul mulțimii $A(n,p)$.

Date de intrare

Fişierul de intrare cardinal.in conţine pe prima linie două numere naturale $n$ și $p$ despărțite printr-un spațiu.

Date de ieşire

Fişierul de ieşire cardinal.out va conţine pe prima linie cardinalul mulțimii $A(n,p)$.

Restricţii şi precizări

• $ 2 \leq n \leq 10^9$
• $ 1 \leq p \leq 10$

Exemplul 1

cardinal.in

15 1

cardinal.out

10

Explicaţii

Sunt $10$ numere naturale mai mici sau egale decât $15$ ce conțin în descompunerea lor în factori primi exponenți mai mici sau egali cu $1$.

Exemplul 2

cardinal.in

27 2

cardinal.out

22

Explicaţii

Sunt $22$ numere naturale mai mici sau egale decât $27$ ce conțin în descompunerea lor în factori primi exponenți mai mici sau egali cu $2$.