Rezolvare completă PbInfo #3301 nrdiv9

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema nrdiv9:

#include <bits/stdc++.h>
using namespace std;
ifstream f("nrdiv9.in");
ofstream g("nrdiv9.out");
int main()
{
    int n, p, q, nmax, k=0;
    f >> n;
    nmax=sqrt(n);
    int ciur[nmax];
    for (int i = 1; i <= nmax; i++)
        ciur[i] = i;
    for (int i = 2; i * i <= nmax; i++)
        if (ciur[i] == i)
        {
            for (int j = i * i; j <= nmax; j += i)
                if (ciur[j] == j)
                    ciur[j] = i;
        }
    for (int i = 2; i <= nmax; i++)
    {
        p = ciur[i]; q = ciur[i / ciur[i]];
        if (p * q == i && q != 1 && p != q)
            k++;
        else
        if (ciur[i] == i)
            if (pow(i, 8) <= n)
                k++;
    }
    g << k;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3301 nrdiv9

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3301 nrdiv9 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!