Editing 3314 - Eratostene3

Sursa: [https://www.pbinfo.ro/probleme/3314/eratostene3 - Eratostene3]
----
== Cerinţa ==
Se dau '''n''' numere naturale nenule. Aflaţi pentru fiecare număr dat '''x''', câte numere naturale nenule mai mici sau egale cu '''x''' sunt prime cu '''x'''?
== Date de intrare ==
Fișierul de intrare '''eratostene3.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 '''eratostene3.out''' va conține pentru fiecare număr '''x''' din fişierul de intrare, numărul de numere naturale nenule mai mici sau egale cu '''x''', prime cu '''x'''. Î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
* numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000'''
== Exemple ==
===Exemplul 1===
; eratostene3.in
: 3
: 4 7 12
; Ieșire
: Datele sunt corecte.
; eratostene3.out
: 2 6 4
===Exemplul 2===
; eratostene3.in
: 3
: 15 11 9
; Ieșire
: Datele sunt corecte.
; eratostene3.out
: 8 10 6
===Exemplul 3===
; eratostene3.in
: 2
: 191824719471 19991
; Ieșire
: Datele nu sunt comform restricțiilor impuse.
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#3314 Eratostene3

def eratostene(vector, n):
    f = open("eratostene2.out", "w")
    for x in vector:
        elem_prime=0
        for j in range(1,x):
            cmmdc=x
            while cmmdc!=j:
                if cmmdc>j:
                    cmmdc-=j
                else: j-=cmmdc
            if cmmdc==1:
                elem_prime+=1
        f.write(str(elem_prime) + " ")


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 > 100000 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 eratosene3.in. Comanda ''with open('eratostene3.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 eccran 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. Se deschide fisierul '''eratostene3.out'''. Se ia fiecare element din '''vector''' iar apoi '''elem_prime''' va retine cate elemente '''j''' mai mici sau egale cu '''x''' are '''x'''. In al doilea for '''j''' ia valori intre 1 si '''x'''. '''cmmdc''' este o copie a lui '''x''' si este o referinta spre cel mai mare divizor comun care, in acest caz, trebuie sa fie 1 ca sa putem adauga j-ul la contorul '''elem_prime'''. In while se efectueaza scaderi repetate pana cand se ajunge la cmmdc-ul dintre '''x''' xi '''j''' si daca la final acesta este 1 se va contoriza. Contorul '''elem_prime''' se va trece in fisier la final pentru fiecare element '''x'''.