Editing 2129 - Prime 1

==Cerința==
Eu sunt fascinată de numerele prime. Consider că numerele prime sunt “scheletul” tuturor numerelor sau “atomii” acestora, pentru că orice număr natural mai mare decât <code>1</code> poate fi scris ca un produs de numere prime. Recent am aflat şi alte proprietăţi interesante legate de numerele prime, de exemplu:

#În şirul Fibonacci există o infinitate de numere prime. Vă mai amintiţi şirul Fibonacci? <code>0</code>, <code>1</code>, <code>1</code>, <code>2</code>, <code>3</code>, <code>5</code>, <code>8</code>, <code>13</code>, <code>...</code> Este şirul în care fiecare termen, exceptând primii doi, se obţine ca suma celor doi termeni care îl precedă.
#Există numere naturale denumite „economice”. Un număr natural este economic dacă numărul de cifre necesare pentru scrierea sa este mai mare decât numărul de cifre necesare pentru scrierea descompunerii sale în factori primi (adică decât numărul de cifre necesare pentru scrierea factorilor primi şi a puterilor acestora). De exemplu <code>128</code> este economic pentru că <code>128</code> se scrie cu <code>3</code> cifre, iar descompunerea sa în factori primi se scrie cu două cifre (<code>2^7</code>); <code>4374</code> este economic pentru că se scrie cu <code>4</code> cifre, în timp ce descompunerea sa în factori primi se scrie cu <code>3</code> cifre (<code>2*3^7</code>). Observaţi că atunci când un factor prim apare la puterea <code>1</code>, aceasta nu este necesar să fie scrisă.
#Multe numere naturale pot fi scrise ca sumă de două numere prime. Dar nu toate. De exemplu, <code>121</code> nu poate fi scris ca sumă de două numere prime.
Scrieţi un program care citeşte numărul natural <code>n</code> şi o secvenţă de n numere naturale, apoi rezolvă următoarele cerinţe:

#determină şi afişează câte dintre numerele din secvenţa dată sunt numere prime din şirul Fibonacci;
#determină şi afişează câte dintre numerele din secvenţa dată sunt numere economice;
#determină şi afişează câte dintre numerele din secvenţa dată nu pot fi scrise ca sumă de două numere prime.

==Date de intrare==
Fișierul de intrare <code>prime1.in</code> conține pe prima linie un număr natural <code>c</code> care reprezintă cerinţa (<code>1</code> , <code>2</code> sau <code>3</code>). Pe a doua linie se află numărul natural <code>n</code>. Pe a treia linie se află o secvenţă de <code>n</code> numere naturale separate prin spaţii.
==Date de ieșire==
Fișierul de ieșire <code>prime1.out</code> va conţine o singură linie pe care va fi scris răspunsul la cerinţa din fişierul de intrare.

==Restricții și precizări==

*<code>1 < n ≤ 50</code>
*Dacă <code>c=1</code> sau <code>c=3</code> numerele naturale din şir sunt mai mari decât <code>1</code> şi mai mici decât <code>10^7</code>.
*Dacă <code>c=2</code> numerele naturale din şir sunt mai mari decât <code>1</code> şi mai mici decât <code>10^14</code>. Pentru rezolvarea corectă a cerinţei 1 se acordă 20 de puncte; pentru rezolvarea corectă a cerinţei 2 se acordă 50 de puncte, iar pentru rezolvarea corectă a cerinţei 3 se acordă 30 de puncte.

==Exemplu 1==
;Intrare
:1
:5
:2 10 13 997 233
;Ieșire
:3

===Explicație===
Cerinţa este 1. Cele <code>3</code> numere prime din şirul Fibonacci existente în secvenţă sunt <code>2</code>, <code>13</code> şi <code>233</code>.

==Exemplu 2==
;Intrare
:2
:4
:128 25 4374 720
;Ieșire
:2

== Explicație ==
Cerinţa este 2. Succesiunea conţine două numere economice (<code>128</code> şi <code>4374</code>).

==Exemplu 3==
;Intrare
:3
:5
:57 30 121 11 3
;Ieșire
:4

===Explicație===
Cerinţa este 3. Sunt <code>4</code> numere naturale din secvenţă care nu pot fi scrise ca sumă de două numere prime: <code>57</code>, <code>121</code>, <code>11</code>, <code>3</code>.

== Exemplu 4 ==

;Intrare
:3 5  57 -30 -121 -11 3
;Ieșire
:Date de intrare gresite!

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2129 Prime 1
import math


def prim(nr):
    if nr <= 1:
        return False
    if nr == 2:
        return True
    if nr % 2 == 0:
        return False

    for i in range(3, int(math.sqrt(nr)) + 1, 2):
        if nr % i == 0:
            return False

    return True


def suma_cifre(nr):
    cifre = [int(x) for x in list(str(nr))]
    return sum(cifre)


def suma_factori_cifre(nr):
    suma = 0
    factor = 2

    while nr > 1:
        e = 0

        if nr % factor == 0:
            while nr % factor == 0:
                nr //= factor
                e += 1
            suma += suma_cifre(factor)
            if e > 1:
                suma += suma_cifre(e)
        factor += 1

        if factor ** 2 > nr:
            factor = nr

    return suma


def prime_suma(nr):
    if nr % 2 == 0:
        return False
    elif prim(nr - 2):
        return False

    return True


def cerinte(c, n, numere):
    if not n == len(numere):
        return False
    if not 1 < n <= 50:
        return False

    if c == 1 or c == 3:
        for nr in numere:
            if not 1 < nr < 10**7:
                return False

    return True


def c_prim_fibonacii(numere):
    nr = 0
    fibonacii = {0}
    a, b = 1, 1

    while a < 10 ** 7:
        fibonacii.add(a)
        temp = a
        a = b
        b += temp

    for numar in numere:
        if numar in fibonacii and prim(numar):
            nr += 1

    return nr


def c_economice(numere):
    nr = 0
    for numar in numere:
        nd = suma_cifre(numar)
        nde = suma_factori_cifre(numar)

        if nd > nde:
            nr += 1

    return nr


def c_not_suma(numere):
    nr = 0
    for numar in numere:
        if prime_suma(numar):
            nr += 1

    return nr


def main():
    c = int(input())
    n = int(input())
    numere = [int(x) for x in input().split()]

    if not cerinte(c, n, numere):
        return print("Date de intrare gresite!")

    if c == 1:
        print(c_prim_fibonacii(numere))

    elif c == 2:
        print(c_economice(numere))

    elif c == 3:
        print(c_not_suma(numere))


if __name__ == "__main__":
    main()

</syntaxhighlight>