Editing 1481 - Gradina Piticului

==  Enunț ==
Un pitic pasionat de numere trebuie să-și pună flori în grădină. El are de plantat m rânduri cu flori, aceeași floare pe tot rândul. Rândurile sunt numerotate de la 1 la m. Având la dispoziție suficiente specii de flori, piticul nostru s-a gândit să le planteze folosind următorul algoritm matematic: pe rândurile care sunt numere prime, va planta exact floarea numerotată cu numărul prim respectiv, iar pe celelalte rânduri va planta floarea numerotată cu suma divizorilor primi ai numărului neprim.
== Cerinţa ==
Să se realizeze un program care să afişeze ordinea de așezare a florilor pe cele '''m''' rânduri.
== Date de intrare ==
Fișierul de intrare '''pitic.in''' conține pe prima linie numărul '''m'''.
== Date de ieşire ==
Dacă datele sunt introduse corect, în fișier se va afișa: '''"Datele sunt introduse corect."''', apoi fişierul de ieşire '''pitic.out''' va conține pe prima linie un șir de '''m''' numere, separate prin câte un spațiu, fiecare număr reprezentând specia de floare ce urmează să fie plantată pe rândul respectiv. În cazul în care datele nu respectă restricțiile, se va afișa în fișier :'''"Datele nu corespund restricțiilor impuse."'''.

== Restricții și precizări ==
* 1 &les; m &les; 1000
== Exemplu ==
; pitic.in
: 6
; pitic.out
: Datele sunt introduse corect.
: 0 2 3 2 5 5

== Rezolvare ==
<syntaxhighlight lang="python" line>

def validare_date(m):
    return 1 <= m <= 1000

def prim(n):
    d = 2
    cnt = 1
    while n > 1:
        p = 0
        while n % d == 0:
            p += 1
            n //= d
        if p > 0:
            cnt *= (p + 1)
        d += 1
        if d * d > n:
            d = n
    if cnt == 2:
        return 1
    else:
        return 0


def sumprim(n):
    s = 0
    d = 2
    while n > 1:
        p = 0
        while n % d == 0:
            p += 1
            n //= d
        if p > 0:
            s += d
        d += 1
        if d * d > n:
            d = n
    return s

if __name__ == "__main__":
    with open("pitic.in") as fin, open("pitic.out", "w") as fout:
        m = int(fin.readline().strip())
        if validare_date(m):
            fout.write("Datele de intrare corespund restrictiilor impuse.\n")
            for i in range(1, m + 1):
                if prim(i):
                    fout.write(str(i) + " ")
                else:
                    fout.write(str(sumprim(i)) + " ")
        else:
            fout.write("Datele de intrare nu corespund restrictiilor impuse.")



</syntaxhighlight>

==Explicație rezolvare ==
Funcția validare_date(m) verifică dacă numărul m este între 1 și 1000, returnând True dacă este și False altfel.<br>Funcția prim(n) verifică dacă numărul n este prim. Mai exact, aceasta determină factorii primi ai lui n și verifică dacă n are exact doi factori primi distincți. Dacă da, atunci n este prim și funcția returnează 1, altfel funcția returnează 0.<br>Funcția sumprim(n) calculează suma divizorilor primi ai lui n, cu excepția lui n . Pentru aceasta, se determină factorii primi ai lui n și se adună doar aceia care sunt prima putere a unui număr prim.<br>În funcția principală, se citește numărul m din fișierul de intrare și se verifică dacă este valid. Dacă da, se scrie mesajul "Datele de intrare corespund restrictiilor impuse." în fișierul de ieșire și se parcurg toate rândurile de la 1 la m. Pentru fiecare rând, se determină dacă este prim și, dacă da, se scrie numărul prim respectiv în fișierul de ieșire. În caz contrar, se calculează suma divizorilor primi ai rândului respectiv și se scrie acea sumă în fișierul de ieșire. Dacă m nu este valid, se scrie în fișierul de ieșire mesajul "Datele de intrare nu corespund restrictiilor impuse."