2325 - prim003

Sursa: - 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 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

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

• 1 ≤ t ≤ 100.000
• 1 ≤ a, b ≤ 1.000.000

Exemple

Exemplul 1

Intrare

3

1 7

10 30

88 100

Ieșire

Datele sunt corecte.

2 7 4

Exemplul 2

Intrare

5

1 10

26 40

15 90

90 111

1431 1530

Ieșire

Datele sunt corecte.

4 6 25 6 24

Exemplul 3

Intrare

2

314515341535441 412351541241

29 49

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<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

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.