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

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()

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