3313 - Eratostene2: Difference between revisions

From Bitnami MediaWiki
mNo edit summary
No edit summary
Line 28: Line 28:
: Datele sunt corecte.
: Datele sunt corecte.
; eratostene2.out
; eratostene2.out
: 3 1 4
: 1 1 3
===Exemplul 3===
===Exemplul 3===
; eratostene2.in
; eratostene2.in
Line 38: Line 38:
== Rezolvare ==  
== Rezolvare ==  
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
#3313 Eratostene2


def eratostene(vector, n):
    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]
    f = open("eratostene2.out", "w")
    for x in vector:
        factori_primi=0
        for j in numere_prime:
            if x==1:
                break;
            elif x%j==0:
                factori_primi+=1
                while x%j==0:
                    x//=j
        f.write(str(factori_primi) + " ")


def conform_restrictiilor():
    vector = list()
    with open('eratostene2.in') as f:
        lines = f.readlines()
        for line in lines:
            for c in line.split():
                if c.isdigit() == True:
                    vector.append(int(c))
    n = vector[0]
    vector = vector[1:]
    if n > 500000 and n < 1:
        print("Datele nu sunt comform restricțiilor impuse.")
        exit()
    for x in vector:
        if x < 0 or x > 1000000:
            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>
</syntaxhighlight>


==Explicaţie cod==
==Explicaţie cod==
In functia main se apeleaza doua functii. Prima functie este '''conform_restrictiilor''' iar a doua este '''eratostene'''.
Functia '''conform_restrictiilor()''' are declarat un vector ce va memora toate valoriile din fisierul de intrare eratosene2.in. Comanda ''with open('eratostene2.in') as f:'' va lua toate liinile din fisier iar apoi fiecare linie pe rand. Se ia fiecare pozitie din aceasta linie si se verifica daca este cifra. Daca este, se va adauga la '''vector'''.
'''n''' ve reprezenta prima valoare din '''vector''' iar apoi '''vector''' va retine restul de valori. Daca '''n''' nu se incadreaza restrictiilor impuse se va iesi din functie cu comanda '''exit()''' iar pe excran se va afisa mesajul "Datele nu sunt comform restricțiilor impuse.". Se verifica apoi daca fiecare valoare din '''vector''' indeplineste restrictiile impuse si daca nu se afiseaza mesajul "Datele nu sunt comform restricțiilor impuse." si se iese cu comanda exit(). Daca pana acum toate datele au fost corecte atunci '''vector''' si '''n''' vor fi returnate spre main.
Functia '''eratostene(vector, n)''' va lua '''vector'''-ul si '''n'''-ul transmise de functia precizata mai sus. Vectorul ''' numere_prime''' are toate numerele prime pana la 100 pentru a face descompunerea in factori primi mai usoara. Se deschide fisierul '''eratostene2.out'''. In for-ul ce urmeaza se iau fiecare elemente pe rand si termenul '''factori_primi''' vor contoriza cate valori se afla in descompunerea de factori primi al lui '''x'''. Parcurgem dupa acea vectorul '''numere_prime''' si verificam daca '''x''' este 1 si daca da, iesim din for pentru ca descompunerea in factori primi s-a incheiat. Daca '''x''' NU este egal cu 1 atunci se verifica daca se divide cu elementul curent al vectorului '''numere_prime''' si daca da atunci crestem contorul '''factori_primi''' si se va imparti '''x''' la divizorul prim de cate ori se poate. La final se va scrie in fisierul de iesire contorul '''factori_primi''' pentru fiecare element din '''vector'''.

Revision as of 14:18, 31 March 2023

Sursa: - Eratostene2


Cerinţa

Se dau n numere naturale. Aflaţi pentru fiecare număr câţi factori primi are în descompunere.

Date de intrare

Fișierul de intrare eratostene2.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

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 eratostene2.out va conține pe prima linie n numere, fiecare reprezentând numărul factorilor primi din descompunerea numărului corespunzător 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 ≤ 500.000
  • numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemple

Exemplul 1

eratostene2.in
7
30 5 44 210 1 35 30030
Ieșire
Datele sunt corecte.
eratostene2.out
3 1 2 4 0 2 6

Exemplul 2

eratostene2.in
3
27 11 90
Ieșire
Datele sunt corecte.
eratostene2.out
1 1 3

Exemplul 3

eratostene2.in
2
191824719471 19991
Ieșire
Datele nu sunt comform restricțiilor impuse.


Rezolvare

<syntaxhighlight lang="python" line>

  1. 3313 Eratostene2

def eratostene(vector, n):

   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]
   f = open("eratostene2.out", "w")
   for x in vector:
       factori_primi=0
       for j in numere_prime:
           if x==1:
               break;
           elif x%j==0:
               factori_primi+=1
               while x%j==0:
                   x//=j
       f.write(str(factori_primi) + " ")


def conform_restrictiilor():

   vector = list()
   with open('eratostene2.in') as f:
       lines = f.readlines()
       for line in lines:
           for c in line.split():
               if c.isdigit() == True:
                   vector.append(int(c))
   n = vector[0]
   vector = vector[1:]
   if n > 500000 and n < 1:
       print("Datele nu sunt comform restricțiilor impuse.")
       exit()
   for x in vector:
       if x < 0 or x > 1000000:
           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

In functia main se apeleaza doua functii. Prima functie este conform_restrictiilor iar a doua este eratostene.

Functia conform_restrictiilor() are declarat un vector ce va memora toate valoriile din fisierul de intrare eratosene2.in. Comanda with open('eratostene2.in') as f: va lua toate liinile din fisier iar apoi fiecare linie pe rand. Se ia fiecare pozitie din aceasta linie si se verifica daca este cifra. Daca este, se va adauga la vector. n ve reprezenta prima valoare din vector iar apoi vector va retine restul de valori. Daca n nu se incadreaza restrictiilor impuse se va iesi din functie cu comanda exit() iar pe excran se va afisa mesajul "Datele nu sunt comform restricțiilor impuse.". Se verifica apoi daca fiecare valoare din vector indeplineste restrictiile impuse si daca nu se afiseaza mesajul "Datele nu sunt comform restricțiilor impuse." si se iese cu comanda exit(). Daca pana acum toate datele au fost corecte atunci vector si n vor fi returnate spre main.

Functia eratostene(vector, n) va lua vector-ul si n-ul transmise de functia precizata mai sus. Vectorul numere_prime are toate numerele prime pana la 100 pentru a face descompunerea in factori primi mai usoara. Se deschide fisierul eratostene2.out. In for-ul ce urmeaza se iau fiecare elemente pe rand si termenul factori_primi vor contoriza cate valori se afla in descompunerea de factori primi al lui x. Parcurgem dupa acea vectorul numere_prime si verificam daca x este 1 si daca da, iesim din for pentru ca descompunerea in factori primi s-a incheiat. Daca x NU este egal cu 1 atunci se verifica daca se divide cu elementul curent al vectorului numere_prime si daca da atunci crestem contorul factori_primi si se va imparti x la divizorul prim de cate ori se poate. La final se va scrie in fisierul de iesire contorul factori_primi pentru fiecare element din vector.