Question

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.

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

Restrictii:
2 ≤ n ≤ 109
1 ≤ p ≤ 10

Exemplu:
Cardinal.in: 15 1
Cardinal.out: 10

Answer 1

#include <iostream>
#include <cmath>
using namespace std;

int main(){
long double n,termeni_scosi=0,cat;
double p,radacina_p;
int i;
//introduce n si p
cin>>n>>p;
//extrage radacina de ordin p+1
radacina_p=pow(n,1.0/(p+1));
//trecem prin toti termenii de la 2 la radacina p+1
for(i=2;i<=(int)radacina_p;i++){
//aflam cati multipli ai lui i sunt in intervalul 2,n
cat=n/pow(i,p+1);
//adunam acesti multipli la termenii care trebuie scosi
termeni_scosi=termeni_scosi+(int)cat;
}
//din n-1 termeni scoatem si termenii numarati mai devreme
cout<<"Cardinal multime:"<<n-1-termeni_scosi;
return 0;
}