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 ⩽ m ⩽ 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.
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.
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.
Î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."