0380 - A Prim 1: Diferență între versiuni
(Pagină nouă: == Cerinţa == Se citește un număr natural și apoi '''n''' numere naturale. Să se determine câte dintre ele sunt aproape prime. == Date de intrare == Programul citește de la tastatură numărul '''n''', și apoi '''n''' numere naturale. == Date de ieşire == Programul afișează pe ecran numărul '''C''', reprezentând câte dintre numerele citite sunt aproape prime. == Restricții și precizări == * '''1 ≤ n ≤ 100''' *cele n numere citite sunt cuprinse între '''1...) |
Fără descriere a modificării |
||
Linia 17: | Linia 17: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
def | def validate_data(n, arr): | ||
if n <= | if not 1 <= n <= 10**5: | ||
return False | return False | ||
for | for a in arr: | ||
if | if not 1 <= a <= 10**9: | ||
return False | return False | ||
return True | return True | ||
if __name__ == '__main__': | |||
n = int(input( | n = int(input()) | ||
arr = list(map(int, input().split())) | |||
if validate_data(n, arr): | |||
print("\nDatele de intrare corespund restrictiilor impuse.\n") | |||
else: | |||
print("Datele de intrare nu corespund restrictiilor impuse.") | |||
cnt = 0 | |||
for i in range(n): | for i in range(n): | ||
x = arr[i] | |||
d = 2 | |||
cn = 1 | |||
while x > 1: | |||
p = 0 | |||
if | while x % d == 0: | ||
p += 1 | |||
x //= d | |||
d += 1 | |||
cn *= (p + 1) | |||
if d * d > x: | |||
d = x | |||
if cn == 4: | |||
cnt += 1 | |||
print( | print(cnt) | ||
</syntaxhighlight> | |||
==Explicație rezolvare== | |||
Acest program primește de la utilizator un număr n și o listă de n numere întregi și verifică dacă acestea respectă anumite restricții. Mai precis, n trebuie să fie un număr întreg între 1 și 10^5 inclusiv, iar fiecare număr din lista arr trebuie să fie un număr întreg între 1 și 10^9 inclusiv. Dacă datele de intrare sunt valide, programul afișează un mesaj de confirmare. | |||
Apoi, programul calculează câte dintre numerele din lista arr au exact 4 divizori. Pentru a face acest lucru, se parcurg toate numerele din lista, iar pentru fiecare număr x, se calculează numărul său de divizori prin factorizarea în factori primi a lui x. Se folosește o metodă eficientă care calculează numărul de divizori al lui x ca produsul (p + 1) pentru fiecare factor prim p ridicat la puterea sa corespunzătoare în factorizarea lui x. Dacă numărul de divizori este 4, se incrementează un contor. La final, programul afișează numărul de numere din lista arr care au exact 4 divizori. |
Versiunea de la data 2 aprilie 2023 18:26
Cerinţa
Se citește un număr natural și apoi n numere naturale. Să se determine câte dintre ele sunt aproape prime.
Date de intrare
Programul citește de la tastatură numărul n, și apoi n numere naturale.
Date de ieşire
Programul afișează pe ecran numărul C, reprezentând câte dintre numerele citite sunt aproape prime.
Restricții și precizări
- 1 ≤ n ≤ 100
- cele n numere citite sunt cuprinse între 1 și 1.000.000.000
Exemplu
- Intrare
- 6
35 55 12 6 25 50
- Ieșire
- 3
Rezolvare
def validate_data(n, arr):
if not 1 <= n <= 10**5:
return False
for a in arr:
if not 1 <= a <= 10**9:
return False
return True
if __name__ == '__main__':
n = int(input())
arr = list(map(int, input().split()))
if validate_data(n, arr):
print("\nDatele de intrare corespund restrictiilor impuse.\n")
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
cnt = 0
for i in range(n):
x = arr[i]
d = 2
cn = 1
while x > 1:
p = 0
while x % d == 0:
p += 1
x //= d
d += 1
cn *= (p + 1)
if d * d > x:
d = x
if cn == 4:
cnt += 1
print(cnt)
Explicație rezolvare
Acest program primește de la utilizator un număr n și o listă de n numere întregi și verifică dacă acestea respectă anumite restricții. Mai precis, n trebuie să fie un număr întreg între 1 și 10^5 inclusiv, iar fiecare număr din lista arr trebuie să fie un număr întreg între 1 și 10^9 inclusiv. Dacă datele de intrare sunt valide, programul afișează un mesaj de confirmare.
Apoi, programul calculează câte dintre numerele din lista arr au exact 4 divizori. Pentru a face acest lucru, se parcurg toate numerele din lista, iar pentru fiecare număr x, se calculează numărul său de divizori prin factorizarea în factori primi a lui x. Se folosește o metodă eficientă care calculează numărul de divizori al lui x ca produsul (p + 1) pentru fiecare factor prim p ridicat la puterea sa corespunzătoare în factorizarea lui x. Dacă numărul de divizori este 4, se incrementează un contor. La final, programul afișează numărul de numere din lista arr care au exact 4 divizori.