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
, undea[i]
şib[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 numerele2
-prime:10,12,14,15,18,20
; - intervalul
[5, 10]
conţine numerele2
-prim2
,6
si10
; - intervalul
[35, 39]
conţine numere2
-prime35, 36, 38, 39
; - intervalul
[3, 4]
nu conţine niciun număr2
-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; }