Cerința

Se dau n perechi de numere naturale, x şi k. Verificaţi pentru fiecare număr x dacă este produs de k numere prime distincte.

Date de intrare

Fișierul de intrare eratostene7.in conține pe prima linie numărul n, iar pe următoarele n linii câte o pereche de numere x şi k, separate prin spaţiu.

Date de ieșire

Fișierul de ieșire eratostene7.out va conține pe primele n linii cuvântul DA sau NU corespunzător celei de-a n-a perechi din fişierul de intrare.

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ x ≤ 1.000.000
1 ≤ k ≤ 100

Exemplu

eratostene7.in

eratostene7.out

NU
DA
NU

Explicație

Numărul 20 nu este produs de 3 numere prime distincte, 30=2•3•5 este produs de trei numere prime distincte, 49 nu este produs de 2 numere prime distincte.

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 Eratostene7:

#include <fstream>
#define N 1000000
using namespace std;
ifstream f("eratostene7.in");
ofstream g("eratostene7.out");
int prod[N+1], p[N+1], fr[N+1];
int i, j, k, x, n;

int main()
{
    p[1] = 1;
    for(i = 1; i <= N; i++)
        prod[i] = 1;
    for(i = 2; i <= N; i++)
        if(p[i]==0){
            fr[i] = 1;
            prod[i] = i;
            j = i+i;
            while(j <= N){
                p[j] = 1;
                fr[j]++;
                prod[j] *= i;
                j = j + i;
            }
        }
    f >> n;
    for(i = 1; i <= n; i++){
        f >> x >> k;
        if(fr[x] != k) g << "NU\n";
        else if(prod[x]==x) g << "DA\n";
             else g << "NU\n";
    }

    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 #3318 Eratostene7

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3318 Eratostene7 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!

Rezolvare completă PbInfo #3318 Eratostene7