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 exact 9 divizori se va afișa valoarea 0.

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;
}