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

4 2
20 7
5 10
35 39
3 4

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.

#include <bits/stdc++.h>

using namespace std;
ifstream cin("pprim.in");
ofstream cout("pprim.out");
int a[33001] , st , dr;
int primeintreele(int a , int b)
{
    int r;
    while(b!=0)
    {
        r = a %b;
        a = b;
        b = r;
    }
    if(a == 1) return 1;
    else return 0;
}
void pprim(int p)
{
    for(int n = 1 ; n <= 33001;++n)
    {
        int cnt = 0;
        for(int i = 1 ; i*i<= n ; ++i)
        {
            if(n%i==0)
            {
                if(primeintreele(i , n/i)==1)cnt++;
            }
        }
        if(cnt==p) a[n]=a[n-1]+1;
        else a[n] = a[n-1];
    }
}
int main()
{
    int n , p , ok = 0 , x , y , st , dr , max = -1;
    cin >> n >> p;
    pprim(p);
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> x >> y;
        int cnt = 0;
        if(x > y){int aux = x ; x = y ; y = aux;}
        if(a[y]-a[x-1] > max) max = a[y]-a[x-1] , st = x , dr = y;
    }
    if(max == -1) cout << "nu exista";
    else cout << st << " " << dr;
}