2325 - prim003: Difference between revisions

From Bitnami MediaWiki
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>

  1. 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.