Editing 3318 - Eratostene7

Sursa: [https://www.pbinfo.ro/probleme/3318/eratostene7 - Eratostene7]
----
== Cerinţa ==
Se dau '''n''' perechi de numere naturale,'''x''' şi '''k'''. Verificaţi pentru fiecare număr '''x''' dacă este produs de '''k''' numere prime distincte.
== Date de intrare ==
Fișierul de intrare '''eratostene7.in''' iar pe următoarele '''n''' linii câte o pereche de numere '''x''' şi '''k''', separate prin spaţiu.
== Date de ieșire == 
Dacă datele sunt introduse corect, pe ecran se va afișa: 
"Datele sunt corecte.", iar apoi in fişierul de ieșire '''eratostene7.out''' va conține pe primele n linii cuvântul '''DA''' sau '''NU''' corespunzător celei de-a n-a perechi din fişierul de intrare. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

== Restricţii şi precizări ==
* 1 ≤ '''n''' ≤ 100.000
* 1 ≤ '''x''' ≤ 1.000.000
* 1 ≤ '''k''' ≤ 100
== Exemple ==
===Exemplul 1===
; eratostene7.in
: 3
: 20 3
: 30 3
: 49 2
; Ieșire
: Datele sunt corecte.
; eratostene7.out
: NU
: DA
: NU
===Exemplul 2===
; eratostene7.in
: 3
: 1 2
: 5 3
: 6 2
; Ieșire
: Datele sunt corecte.
; eratostene7.out
: NU
: NU
: DA
===Exemplul 3===
; eratostene7.in
: 2
: 191824719471 19991
: 9 3
; Ieșire
: Datele nu sunt comform restricțiilor impuse.
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>

#3318

def eratostene(vector, n):
    f = open("eratostene7.out", "w")
    numere_prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
    for i in range(0, len(vector)):
        x, k = vector[i]
        este_valid = 1
        factori_primi = 0
        for j in numere_prime:
            if x % j == 0:
                numar_factori_primi = 0
                factori_primi += 1
                while x % j == 0:
                    x //= j
                    numar_factori_primi += 1
                if numar_factori_primi != 1:
                    este_valid = 0
        if factori_primi != k:
            este_valid = 0
        if este_valid == 1:
            f.write("DA\n")
        else:
            f.write("NU\n")


def conform_restrictiilor():
    vector = list()
    with open('eratostene7.in') as f:
        n = int(f.readline())
        vector = []
        for line in f:
            x, k = map(int, line.split())
            vector.append((x, k))
    if n > 500000 and n < 1:
        print("Datele nu sunt comform restricțiilor impuse.")
        exit()
    for x, k in vector:
        if x < 0 or x > 100000 or k < 1 or k > 100:
            print("Datele nu sunt comform restricțiilor impuse.")
            exit()
    print("Datele sunt corecte.")
    return vector, n


if __name__ == '__main__':
    vector, n = conform_restrictiilor()
    eratostene(vector, n)



</syntaxhighlight>

==Explicaţie cod==

Acest program primește date de intrare din fișierul '''eratostene7.in''', și verifică pentru fiecare număr '''x''' dacă poate fi descompus în produsul a '''k''' numere prime distincte. Rezultatele verificărilor sunt scrise în fișierul '''eratostene7.out'''.

Funcția '''conform_restrictiilor()''' citește datele de intrare din fișier și verifică dacă sunt conforme cu restricțiile impuse de enunțul problemei. Dacă acestea nu sunt conforme, programul afișează un mesaj de eroare și se încheie. În cazul în care datele sunt conforme, funcția returnează o listă '''vector''' cu perechile de numere '''x''' și '''k''', și variabila '''n''' care indică numărul de perechi.

Funcția '''eratostene()''' primește aceste date și începe să verifice fiecare număr '''x''' din perechile date. Înainte de a verifica dacă '''x''' este produsul a '''k''' numere prime distincte, se generează o listă '''numere_prime''' cu primele 25 de numere prime, de la 2 la 97.

Pentru fiecare număr prim din această listă, programul verifică dacă numărul x este divizibil cu acesta. În cazul în care x este divizibil cu numărul prim, se încearcă descompunerea lui în factori primi, până când nu mai poate fi împărțit. Dacă numărul prim apare mai mult de o dată în descompunerea lui x, variabila '''este_valid''' este setată la 0.

După ce toți factorii primi au fost verificați, programul verifică dacă numărul '''x''' a fost descompus în '''k''' factori primi distincti. Dacă acest lucru nu este adevărat, variabila '''este_valid''' este setată la 0.

La final, în fișierul '''eratostene7.out''' este scris un răspuns pentru fiecare pereche '''x''' și '''k''', corespunzător cu rezultatul verificării de mai sus. Răspunsul poate fi '''DA''' dacă '''x''' poate fi descompus în produsul a '''k''' numere prime distincte sau '''NU''' în caz contrar.