2325 - prim003: Difference between revisions
Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/2325/prim003 - prim003] ---- == Cerinţa == Anul '''2017''' tocmai s-a încheiat, suntem trişti deoarece era număr prim, însă avem şi o veste bună, anul 2018 este produs de două numere prime, '''2''' şi '''1009'''. Dorel, un adevărat colecţionar de numere prime, şi-a pus întrebarea: “Câte numere dintr-un interval [a,b] se pot scrie ca produs de două numere prime? “. == Date de intrare == Programul citește de la tastatu... |
|||
(One intermediate revision by the same user not shown) | |||
Line 25: | Line 25: | ||
; Intrare | ; Intrare | ||
: 5 | : 5 | ||
: | : 1 10 | ||
: | : 26 40 | ||
: | : 15 90 | ||
: | : 90 111 | ||
: | : 1431 1530 | ||
; Ieșire | ; Ieșire | ||
: Datele sunt corecte. | : Datele sunt corecte. | ||
: | : 4 6 25 6 24 | ||
===Exemplul 3=== | ===Exemplul 3=== | ||
; Intrare | ; Intrare | ||
Line 43: | Line 43: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
#2325 prim003 | |||
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 conform_restrictiilor(vector,t): | |||
for i in range(0, t*2,2): | |||
a = vector[i] | |||
b = vector[i+1] | |||
if a <= 0 or b <= 0 or a > 1000000 or b > 1000000 or a > b or t > 100000 or t < 1: | |||
print("Datele nu sunt conform restricțiilor impuse.") | |||
return False | |||
print("Datele sunt corecte.") | |||
return True | |||
if __name__ == '__main__': | |||
t = int (input()) | |||
vector = list() | |||
for _ in range(t): | |||
a , b = map(int,input().split()) | |||
vector.append(a) | |||
vector.append(b) | |||
if conform_restrictiilor(vector,t) is True: | |||
for i in range(0, t*2,2): | |||
a = vector[i] | |||
b = vector[i+1] | |||
contor = 0 | |||
for numere in range(a, b+1): | |||
for i in range(2, numere): | |||
if este_prim(i) and numere % i == 0 and este_prim(numere // i): | |||
contor += 1 | |||
break | |||
print(contor,end=' ') | |||
Line 49: | Line 88: | ||
==Explicaţie cod== | ==Explicaţie cod== | ||
Acest cod implementează un program care primește ca intrare un număr întreg '''t''' și apoi '''t''' perechi de numere întregi '''a''' și '''b'''. Programul numără câte perechi de numere primesc un număr compus din produsul a două numere prime. Programul verifică dacă datele de intrare sunt conforme cu restricțiile impuse și afișează un mesaj corespunzător dacă nu sunt. Pentru a verifica dacă un număr este prim, programul utilizează funcția '''este_prim'''. | |||
Funcția '''conform_restrictiilor''' verifică dacă valorile '''a''' și '''b''' din fiecare pereche de numere întregi sunt cuprinse în intervalul [1, 1 000 000], iar dacă '''t''' se află în intervalul [1, 100 000]. Dacă valorile dintr-o pereche de numere sunt în afara intervalului sau '''a''' este mai mare decât '''b''', funcția va returna False și va afișa un mesaj corespunzător. | |||
În funcția '''main''', programul primește datele de intrare sub forma unui număr întreg '''t''' și a unei liste de perechi de numere întregi. Dacă datele sunt conforme cu restricțiile impuse, programul va număra câte perechi de numere primesc un număr compus din produsul a două numere prime folosind un contor și afișează numărul la ieșire. |
Latest revision as of 15:00, 30 April 2023
Sursa: - prim003
Cerinţa[edit | edit source]
Anul 2017 tocmai s-a încheiat, suntem trişti deoarece era număr prim, însă avem şi o veste bună, anul 2018 este produs de două numere prime, 2 şi 1009. Dorel, un adevărat colecţionar de numere prime, şi-a pus întrebarea: “Câte numere dintr-un interval [a,b] se pot scrie ca produs de două numere prime? “.
Date de intrare[edit | edit source]
Programul citește de la tastatură numărul natural t, iar apoi t perechi de numere naturale a,b cu a≤b, separate prin spații.
Date de ieșire[edit | edit source]
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi va afișa pe ecran, pentru fiecare pereche a,b, numărul numerelor din intervalul [a,b] care se pot scrie ca produs de două numere prime. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".
Restricţii şi precizări[edit | edit source]
- 1 ≤ t ≤ 100.000
- 1 ≤ a, b ≤ 1.000.000
Exemple[edit | edit source]
Exemplul 1[edit | edit source]
- Intrare
- 3
- 1 7
- 10 30
- 88 100
- Ieșire
- Datele sunt corecte.
- 2 7 4
Exemplul 2[edit | edit source]
- Intrare
- 5
- 1 10
- 26 40
- 15 90
- 90 111
- 1431 1530
- Ieșire
- Datele sunt corecte.
- 4 6 25 6 24
Exemplul 3[edit | edit source]
- Intrare
- 2
- 314515341535441 412351541241
- 29 49
- Ieșire
- Datele nu sunt comform restricțiilor impuse.
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line>
- 2325 prim003
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 conform_restrictiilor(vector,t):
for i in range(0, t*2,2): a = vector[i] b = vector[i+1] if a <= 0 or b <= 0 or a > 1000000 or b > 1000000 or a > b or t > 100000 or t < 1: print("Datele nu sunt conform restricțiilor impuse.") return False print("Datele sunt corecte.") return True
if __name__ == '__main__':
t = int (input()) vector = list() for _ in range(t): a , b = map(int,input().split()) vector.append(a) vector.append(b) if conform_restrictiilor(vector,t) is True: for i in range(0, t*2,2): a = vector[i] b = vector[i+1] contor = 0 for numere in range(a, b+1): for i in range(2, numere): if este_prim(i) and numere % i == 0 and este_prim(numere // i): contor += 1 break print(contor,end=' ')
</syntaxhighlight>
Explicaţie cod[edit | edit source]
Acest cod implementează un program care primește ca intrare un număr întreg t și apoi t perechi de numere întregi a și b. Programul numără câte perechi de numere primesc un număr compus din produsul a două numere prime. Programul verifică dacă datele de intrare sunt conforme cu restricțiile impuse și afișează un mesaj corespunzător dacă nu sunt. Pentru a verifica dacă un număr este prim, programul utilizează funcția este_prim.
Funcția conform_restrictiilor verifică dacă valorile a și b din fiecare pereche de numere întregi sunt cuprinse în intervalul [1, 1 000 000], iar dacă t se află în intervalul [1, 100 000]. Dacă valorile dintr-o pereche de numere sunt în afara intervalului sau a este mai mare decât b, funcția va returna False și va afișa un mesaj corespunzător.
În funcția main, programul primește datele de intrare sub forma unui număr întreg t și a unei liste de perechi de numere întregi. Dacă datele sunt conforme cu restricțiile impuse, programul va număra câte perechi de numere primesc un număr compus din produsul a două numere prime folosind un contor și afișează numărul la ieșire.