1823 - P Prim

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.

Încărcare soluție

Lipește codul aici

import sys

a = 0
v = 0
i = 0
n = 0
p = 0
b = 0
a1 = 0
b1 = 0
x = 0
y = 0
nr = 0
j = 0
k = 0
l = 0
r = 0
nr1 = 0
aux = 0

def main():
    max_val = 0
    with open("pprim.in", "r") as f:
        with open("pprim.out", "w") as g:
            n, p = map(int, f.readline().split())
            max_val = 0
            for i in range(1, n+1):
                a, b = map(int, f.readline().split())
                if a > b:
                    aux = a
                    a = b
                    b = aux
                nr1 = 0
                for j in range(a, b+1):
                    nr = 0
                    for k in range(1, j//2):
                        if j % k == 0:
                            x = k
                            y = j // k
                            if x < y:
                                while y:
                                    r = x % y
                                    x = y
                                    y = r
                                if x == 1:
                                    nr += 1
                    if nr == p:
                        nr1 += 1
                if nr1 >= max_val:
                    max_val = nr1
                    a1 = a
                    b1 = b
            if max_val == 0:
                g.write("nu exista")
            else:
                g.write(str(a1) + " " + str(b1))

if __name__ == "__main__":
    main()