3459 - Count Prime

Cerinţa

Să se calculeze cate numere prime sunt în intervalul [stanga, dreapta].

Date de intrare

Fișierul de intrare countprime.in conține pe prima linie două numere stanga și dreapta.

Date de ieşire

Fișierul de ieșire countprime.out va conține pe prima linie numărul cnt, reprezentând numărul de numere prime din intervalul dat.

Restricții și precizări

• 1 ⩽ stanga ⩽ dreapta ⩽ 2 ** 32
• dreapta - stanga ⩽ 1.000.000

Exemplu

countprime.in

2 10

countprime.out

Datele introduse corespund restricțiilor impuse.

4

Explicație

Sunt 4 numere prime în intervalul [2, 10].

Rezolvare

<syntaxhighlight lang="python" line>

def validare_date(stanga, dreapta):

   flag = False
   if stanga.isdigit() and dreapta.isdigit():
       if 0 < int(stanga) < int(dreapta) <= 2 ** 32 and int(dreapta) - int(stanga) <= 1_000_000:
           flag = True

   return flag

def is_prime(n):

   """Verifică dacă un număr este prim."""
   if n < 2:
       return False
   for i in range(2, int(n ** 0.5) + 1):
       if n % i == 0:
           return False
   return True

def count_primes(stanga, dreapta):

   """Calculează câte numere prime sunt în intervalul [stanga, dreapta]."""
   count = 0
   for n in range(stanga, dreapta + 1):
       if is_prime(n):
           count += 1
   return count

if __name__ == "__main__":

   with open('countprime.in', 'r') as fin:
       stanga, dreapta = fin.readline().split()

   if validare_date(stanga, dreapta):
       cnt = count_primes(int(stanga), int(dreapta))
       with open('countprime.out', 'w') as fout:
           fout.write(str(cnt))
       print("\nDatele introduse corespund restricțiilor impuse.\n")
       print("Numărul de numere prime în intervalul [{}, {}] este: {}".format(stanga, dreapta, cnt))
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>