2117 - Divizori 2

Cerinţa

Marinel a învăţat la şcoală despre divizibilitatea numerelor naturale. Un număr natural nenul a este divizor al numărului natural nenul b dacă restul împărţirii lui b la a este 0. De exemplu, numărul 3 este divizor al lui 12 iar numărul 4 nu este divizor al lui 15. Un număr natural nenul n este număr prim dacă are doar 2 divizori: 1 şi n. De exemplu, numărul 7 este număr prim deoarece îi are ca divizori doar pe 1 şi 7 iar numărul 21 nu este număr prim deoarece îi are ca divizori pe 1, 3, 7 şi 21. Scrieţi un program care să îl ajute pe Marinel să îşi verifice tema primită pentru acasă.

Fiind date numărul n al numerelor din şir şi numerele din şir, să se determine: 1) divizorii celui mai mare număr din şir, inclusiv 1 şi el însuşi; 2) numerele prime din şir; 3) numerele care sunt divizori ai tuturor numerelor din şir.

Date de intrare

Fişierul de intrare divizori2in.txt conține pe prima linie un număr natural P, pe a doua linie un număr natural n reprezentând numărul de numere din şir şi pe a treia linie cele n numere naturale din şir, separate prin spaţii.

Date de ieșire

Dacă valoarea lui P este 1, se va rezolva numai punctul 1) din cerinţă: fişierul divizori2out.txt va conţine pe prima linie doar divizorii celui mai mare număr din şir. Dacă valoarea lui P este 2, se va rezolva doar punctul 2) din cerinţă: fişierul divizori2out.txt va conţine pe prima linie doar numerele prime din şir sau numărul -1 dacă şirul nu conţine numere prime. Dacă valoarea lui P este 3, se va rezolva numai punctul 3) din cerinţă: fişierul divizori2out.txt va conţine pe prima linie doar numerele care sunt divizori ai tuturor numerelor din şir.

Restricţii şi precizări

• valoarea lui P poate să fie doar 1 sau 2 sau 3;
• numărul natural n este cuprins între 2 şi 1000;
• numerele din şir sunt numere naturale nenule cu cel mult 6 cifre;
• pentru rezolvarea corectă a primei cerinţe se acordă 30 de puncte;
• pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 30 de puncte;
• pentru rezolvarea corectă a celei de-a treia cerinţe se acordă 40 de puncte;

Exemplu

divizori2in.txt

1
7
12 18 8 4 13 6 17

divizori2out.txt

Datele de intrare corespund restrictiilor impuse
1 2 3 6 9 18

Exemplu 2

divizori2in.txt

2
7
12 18 8 4 13 6 17

divizori2out.txt

Datele de intrare corespund restrictiilor impuse
13 17

Exemplu 3

divizori2in.txt

4
7
12 18 8 4 13 6 17

divizori2out.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> def divizori(n):

   div = [1, n]
   for i in range(2, int(n**0.5) + 1):
       if n % i == 0:
           div.append(i)
           if n // i != i:
               div.append(n // i)
   return sorted(div)

def este_prim(n):

   if n < 2:
       return False
   for i in range(2, int(n**0.5) + 1):
       if n % i == 0:
           return False
   return True

def validare(p, n, sir):

   if p not in [1, 2, 3]:
       return False, "Datele de intrare nu corespund restrictiilor impuse"
   if not 2 <= n <= 1000:
       return False, "Datele de intrare nu corespund restrictiilor impuse"
   for val in sir:
       if not isinstance(val, int) or not 1 <= val <= 10**6:
           return False, "Datele de intrare nu corespund restrictiilor impuse"
   return True, "Datele de intrare corespund restrictiilor impuse"

def main():

   with open('divizori2in.txt', 'r') as fin:
       p = int(fin.readline().strip())
       n = int(fin.readline().strip())
       sir = list(map(int, fin.readline().split()))

   valid, message = validare(p, n, sir)
   with open('divizori2out.txt', 'w') as fout:
       fout.write(message + '\n')
       if not valid:
           return

   if p == 1:
       max_n = max(sir)
       rez = divizori(max_n)
   elif p == 2:
       rez = [x for x in sir if este_prim(x)]
       if len(rez) == 0:
           rez = [-1]
   else:  # P == 3
       rez = []
       for x in sir:
           if all(y % x == 0 for y in sir):
               rez.append(x)

   with open('divizori2out.txt', 'a') as fout:
       fout.write(' '.join(map(str, rez)) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

• P=1 deci se rezolvă prima cerinţă.
• Cel mai mare număr din şir este 18
• Divizorii numărului 18 sunt 1, 2, 3, 6, 9 şi 18