3318 - Eratostene7

Sursa: - 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.

Rezolvare

#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)

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.