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 1 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?
0,1,1,2,3,5,8,13,...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
128este economic pentru că128se scrie cu3cifre, iar descompunerea sa în factori primi se scrie cu două cifre (2^7);4374este economic pentru că se scrie cu4cifre, în timp ce descompunerea sa în factori primi se scrie cu3cifre (2*3^7). Observaţi că atunci când un factor prim apare la puterea1, aceasta nu este necesar să fie scrisă. - Multe numere naturale pot fi scrise ca sumă de două numere prime. Dar nu toate. De exemplu,
121nu poate fi scris ca sumă de două numere prime.
Scrieţi un program care citeşte numărul natural n ş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 prime1.in conține pe prima linie un număr natural c care reprezintă cerinţa (1 , 2 sau 3). Pe a doua linie se află numărul natural n. Pe a treia linie se află o secvenţă de n numere naturale separate prin spaţii.
Date de ieșire
Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."
Pe următorul rând se va afișa răspunsul la cerinţa din fişierul de intrare.
În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."
Restricții și precizări
1 < n ≤ 50- Dacă
c=1sauc=3numerele naturale din şir sunt mai mari decât1şi mai mici decât10^7. - Dacă
c=2numerele naturale din şir sunt mai mari decât1şi mai mici decât10^14. 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
- Datele de intrare corespund restricțiilor impuse.
- 3
Explicație
Cerinţa este 1. Cele 3 numere prime din şirul Fibonacci existente în secvenţă sunt 2, 13 şi 233.
Exemplu 2
- Intrare
- 2
- 4
- 128 25 4374 720
- Ieșire
- Datele de intrare corespund restricțiilor impuse.
- 2
Explicație
Cerinţa este 2. Succesiunea conţine două numere economice (128 şi 4374).
Exemplu 3
- Intrare
- 3
- 5
- 57 30 121 11 3
- Ieșire
- Datele de intrare corespund restricțiilor impuse.
- 4
Explicație
Cerinţa este 3. Sunt 4 numere naturale din secvenţă care nu pot fi scrise ca sumă de două numere prime: 57, 121, 11, 3.
Exemplu 4
- Intrare
- 3
- 5
- 57 -30 -121 -11 3
- Ieșire
- Datele de intrare nu corespund restricțiilor impuse.
Rezolvare
#2129 Prime 1
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 prim(nr):
# Dace nr <= 1, atunci nr nu este prim.
if nr < 2:
return False
# Dacă de la 2 până la rădăcina pătrată a lui nr există un divizor a lui nr, atunci nr nu este prim.
for i in range(2, int(nr**0.5) + 1):
if nr % i == 0:
return False
return True
def suma_cifre(nr):
# Transformăm numărul într-o listă de cifre, după care returnăm suma cifrelor
cifre = [int(x) for x in list(str(nr))]
return sum(cifre)
def suma_factori_cifre(nr):
suma = 0
# Primul factor prim este 2
factor = 2
while nr > 1:
exponent = 0
# Dacă numărul este divizibil cu factorul curent...
if nr % factor == 0:
# ...îl împărțim la factorul curent și numărăm de câte ori apare factorul curent în număr
while nr % factor == 0:
nr //= factor
exponent += 1
# Adăugăm la sumă suma cifrelor factorului și a exponentului, dacă exponentul este mai mare decât 1
suma += suma_cifre(factor)
if exponent > 1:
suma += suma_cifre(exponent)
# Trecem la următorul factor prim
factor += 1
# Dacă factorul prim la pătrat este mai mare decât numărul, atunci numărul este prim
if factor ** 2 > nr:
factor = nr
return suma
def prime_suma(nr):
# Dacă nr este par sau nr-2 este prim, atunci nr nu este sumă de două numere prime.
if nr % 2 == 0:
return False
elif prim(nr - 2):
return False
return True
def c_prim_fibonacii(numere):
nr = 0
fibonacii = {0}
a, b = 1, 1
# Generăm numere Fibonacii până ajungem la 10^7
while a < 10 ** 7:
# Algoritm pentru a genera numerele din șirul lui Fibonacci
fibonacii.add(a)
temp = a
a = b
b += temp
# Pentru fiecare număr din numere...
for numar in numere:
# ...dacă numărul se află în șirul lui Fibonacci și este prim...
if numar in fibonacii and prim(numar):
# ...îl numărăm
nr += 1
return nr
def c_economice(numere):
nr = 0
for numar in numere:
nr_suma_cifre = suma_cifre(numar)
nde = suma_factori_cifre(numar)
if nr_suma_cifre > 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 prime1(c, numere):
# c este numărul cerinței
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__":
c = int(input())
n = int(input())
numere = [int(x) for x in input().split()]
if not cerinte(c, n, numere):
print("Datele de intrare nu corespund restricțiilor impuse.")
else:
print("Datele de intrare corespund restricțiilor impuse.")
prime1(c, numere)
