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

#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=' ')

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.