Cerința
Se dă un număr natural n
. Să se scrie un program care determină și afișează pe ecran numărul de numere mai mici sau egale cu n
care au exact 9
divizori.
Date de intrare
Programul citește din fișierul nrdiv9.in
numărul n
.
Date de ieșire
Programul scrie în fișierul nrdiv9.out
numărul k
, reprezentând numărul de numere mai mici sau egale cu n
care au exact 9
divizori.
Restricții și precizări
1 ≤ n ≤ 1.000.000.000
;- dacă nu există numere mai mici sau egale cu
n
care au exact9
divizori se va afișa valoarea0
.
Exemplul 1:
nrdiv9.in
100
nrdiv9.out
2
Explicație
Sunt 2
numere mai mici sau egale cu 100
care au exact 9
divizori: 36
și 100
.
Exemplul 2:
nrdiv9.in
1000
nrdiv9.out
8
Explicație
Sunt 8
numere mai mici sau egale cu 1000
care au exact 9
divizori: 36
, 100
, 196
, 225
, 256
, 441
, 484
, 676
.
#include <bits/stdc++.h> using namespace std; ifstream cin("nrdiv9.in"); ofstream cout("nrdiv9.out"); int main(){ int n; cin >> n; int cc = 0; for(int i = 1; i * i <= n; ++i){ int x = i; int d = 2, cnt = 1; while(x > 1){ int p = 0; while(x % d == 0) p++, x/=d; cnt=cnt * (2 * p + 1); d++; if(d * d > x) d = x; } if(cnt == 9) cc++; } cout << cc; }