1479 - Pretios

Cerință

Un număr natural în baza 10 se numește prețios dacă numărul de cifre ale sale din baza 2 este număr prim. Se dă un interval [a,b]. Determinați câte numere prețioase se află în acest interval.

Date de intrare

Programul citește de la tastatură numerele a și b.

Date de ieșire

Programul va afișa pe ecran numărul x, reprezentând numărul de numere prețioase din intervalul dat.

Restricții de precizări

• 1 ⩽ a, b ⩽ 10.000.000.000.000.000.000

Exemplu

Exemplul 1

Intrare

1

4

Ieșire

Datele introduse corespund restricțiilor impuse.

3

Explicație

Cele 3 numere prețioase sunt 2 3 4.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1"> import math

def is_prime(n):

   if n < 2:
       return False
   for i in range(2, int(math.sqrt(n)) + 1):
       if n % i == 0:
           return False
   return True

def count_precious_numbers(a, b):

   count = 0
   for num in range(a, b + 1):
       binary_digits = bin(num)[2:]
       if is_prime(len(binary_digits)):
           count += 1
   return count

if __name__ == '__main__':

   a = int(input("Introduceți numărul a: "))
   b = int(input("Introduceți numărul b: "))

   if 1 <= a <= b <= 10 ** 18:
       print("Datele de intrare corespund restricțiilor impuse.")
       result = count_precious_numbers(a, b)
       print("Numărul de numere prețioase din intervalul dat este:", result)
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>