0498 - NumararePIE

Sursa: - NumararePIE

---

Cerinţe

Se dă un vector cu n numere naturale. Să se determine câte dintre perechile de elemente din vector sunt prime între ele.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spaţii, reprezentând elementele vectorului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează pe ecran numărul C, reprezentând valoarea cerută. În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ⩽ n ⩽ 200
• elementele vectorului vor fi cuprinse între 0 și 1000

Exemple

Exemplul 1

Intrare

6

51 18 15 28 77 121

Ieșire

Datele sunt introduse corect.

9

Explicație exemplul 1

Perechile de elemente prime între ele sunt:
51 28
51 77
51 121
18 77
18 121
15 28
15 77
15 121
28 121

Exemplul 2

Intrare

5

10 2 -3 4 5

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

# 0498

def verificare_prime_intre_ele(nr1, nr2):
    while nr2 != 0:
        a = nr1 % nr2
        nr1 = nr2
        nr2 = a
    return nr1


def numarare_perechi_elem_prime_intre_ele(vector, n):
    C = 0
    for i in range(n):
        for j in range(i + 1, n):
            if verificare_prime_intre_ele(vector[i], vector[j]) == 1:
                C += 1
    print(C)


def citire_conform_restrictiilor(vector, n):
    if n < 1 or n > 200:
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    for x in vector:
        if x < 0 or x > 1000:
            print("Datele nu corespund restricțiilor impuse.")
            exit()
    if n != len(vector):
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    print("Datele sunt introduse corect.")


if __name__ == '__main__':
    n = int(input())
    vector = list(map(int, input().split()))
    citire_conform_restrictiilor(vector, n)
    numarare_perechi_elem_prime_intre_ele(vector, n)

Explicație rezolvare

   Programul de mai sus conține trei funcții, funcția verificare_prime_intre_ele(nr1, nr2), funcția numarare_perechi_elem_prime_intre_ele(vector, n) și funcția citire_conform_restrictiilor(vector, n), care se vor rula în interiorul main-ului (if __name__ == '__main__' , linia 34) după citirea numărului n (linia 35) și celor n numere pe care le vom pune în șirul „vector” (linia 36).
   După ce am citit elementele, se va apela funcția citire_conform_restrictiilor(vector, n) care primește doi parametri: vectorul „vector” și lungimea sa, reprezentată de variabila „n”. Funcția verifică dacă n este între 1 și 200 (linia 21), dacă elementele vectorului sunt cuprinse între 0 și 1000 (liniile 24, 25) și dacă n este lungimea vectorului „vector” (linia 28). Dacă oricare dintre condiții este încălcată, se va afișa mesajul „Datele nu corespund restricțiilor impuse.” și se va ieși din program cu comanda exit(). Dacă toate condițiile sunt respectate, se va afișa mesajul „Datele sunt introduse corect.” (linia 31) și se va continua programul.
   Dacă s-au introdus corect datele, se va apela funcția numarare_perechi_elem_prime_intre_ele(vector, n) care primește ca parametrii vectorul „vector” și dimensiunea sa „n”. În această funcție se inițializează o variabilă C cu 0,  care va fi utilizată pentru a număra perechile de elemente consecutive din vector care sunt prime între ele, apoi se parcurge vectorul utilizând o buclă for. În interiorul primei bucle for, se adaugă o buclă for imbricată care începe de la i + 1 (următorul element din vector după elementul curent) și se termină la n-1 (ultimul element din vector). Aceasta se face pentru a verifica toate perechile de elemente consecutive posibile din vector. Pentru fiecare pereche de elemente consecutive din vector, se apelează funcția verificare_prime_intre_ele(nr1, nr2) pentru a verifica dacă acestea sunt prime între ele. Funcția verificare_prime_intre_ele(nr1, nr2) calculează cel mai mare divizor comun al celor două numere folosind algoritmul lui Euclid (care începe prin a calcula restul împărțirii nr1 la nr2 și se atribuie rezultatul într-o variabilă a (adesea denumită și "restul"), apoi se actualizează valorile celor două numere astfel: nr1 devine nr2 și nr2 devine a. și se repetă acești pași până când a devine 0, și vom avea în final CMMD al celor două numere) și returnează rezultatul. Dacă rezultatul returnat de această funcție este 1 (adică cele două numere nu au niciun divizor comun în afara valorii 1), atunci se consideră că cele două numere sunt prime între ele.
-> dacă cele două numere consecutive din vector sunt prime între ele, atunci variabila C este incrementată cu 1;
-> la finalul buclei imbricate, se va obține numărul total de perechi de elemente consecutive din vector care sunt prime între ele, stocat în variabila C, pe care o afișăm, ea fiind valoarea cerută în problemă.