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