Cerința

Un număr natural nenul se numeste “p-prim” dacă el se descompune în p moduri ca produs de doi factori primi între ei. De exemplu, numărul 60 este 4-prim deoarece 60 se decompune în 4 moduri ca produs de doi factori primi între ei 60=1*60=4*15=5*12=20*3, iar numărul 7 este 1-prim. Pentru un interval închis [a,b] să se determine câte numere p-prime aparţin intervalului. De exemplu intervalul [7, 20] conţine numerele 2-prime: 10,12, 14,18,20.

Date de intrare

Din fişierul de intrare pprim.in se citesc de pe prima linie două numere naturale N şi P şi de pe urmatoarele N linii câte două numere ce reprezintă capetele unui interval.

Date de ieșire

În fişierul de ieşire pprim.out se va scrie pe prima linie intervalul cu cele mai multe numere p-prime. Extremitatile intervalului se vor afisa in ordine crecatoare. Dacă există mai multe intervale cu același număr se va afișa ultimul interval citit. Dacă NU există niciun interval se va afișa mesajul nu exista.

Restricții și precizări

3 ≤ N ≤ 1000
1 ≤ P ≤ 1000
1 ≤ a[i],b[i] ≤ 33000, unde a[i] şi b[i] sunt capetele intervalelor, i=1,2,..N

Exemplu

pprim.in

pprim.out

7 20

Explicație

Intervalul [7, 20] conţine numerele 2-prime: 10,12,14,15,18,20;
intervalul [5, 10] conţine numerele 2-prim 2, 6 si 10;
intervalul [35, 39] conţine numere 2-prime 35, 36, 38, 39;
intervalul [3, 4] nu conţine niciun număr 2-prim.

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

#include <fstream>
using namespace std;
int a,v,i,n,p,b,a1,b1,x,y,nr,j,k,l,r,nr1,aux;
int main()
{
    int max=0;
    ifstream f("pprim.in");
    ofstream g("pprim.out");
    f>>n>>p;
    max=0;
    for(i=1;i<=n;i++)
    {
        f>>a>>b;
        if(a>b)
        {
            aux=a;
            a=b;
            b=aux;
        }
        nr1=0;
        for(j=a;j<=b;j++)
        {
            nr=0;
            for(k=1;k<=j/2;k++)
                if (j%k==0)
                //for (l=k+1;l<=j;l++)
                {
                 x=k;y=j/k;//g<<x<<" "<<y;
                    if(x<y)
                    {
                        while(y)
                        {
                            r=x%y;
                            x=y;
                            y=r;
                        }
                        if (x==1)
                        {
                            nr++;
                        }
                    }
                  }
          if(nr==p)
          {
              nr1++;//g<<j<<" ";
          }
        }
        if(nr1>=max)
        {
            max=nr1;
            a1=a;
            b1=b;
        }
      //g<<endl;
    }
    if(max==0)
        g<<"nu exista";
    else
        g<<a1<<" "<<b1;
    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 #1823 PPrim

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