4139 - triprime

Enunţ

Un număr se numește triprim dacă este produsul a trei numere prime distincte. Exemple de numere triprime: 30 = 2 × 3 × 5, 42 = 2 × 3 × 7, 231 = 3 × 7 × 11. Exemple de numere care nu sunt triprime: 77 = 7 × 11 (prea puține numere prime în produs), 3003 = 3 × 7 × 11 × 13 (prea multe numere prime în produs), 18 = 2 × 3 × 3 (numerele prime nu sunt distincte), 10241 = 7 × 7 × 11 × 19 (prea multe numere prime în produs).

Cerința

Date fiind numerele A și B, să se afișeze numărul de numere triprime din intervalul [A, B] (inclusiv A și B).

Date de intrare

Fișierul de intrare triprime.in conține pe prima linie două numere naturale A și B, despărțite printr-un singur spațiu.

Date de ieșire

Fișierul de ieșire triprime.out va conține numărul de numere triprime din intervalul [A, B].

Restricții și precizări

• 1 ≤ A ≤ B ≤ 390.000.000
• Pentru 18 puncte, 1 ≤ B ≤ 1.500.000
• Pentru 6 puncte, 1.500.000 < B ≤ 2.500.000
• Pentru 20 puncte, 2.500.000 < B ≤ 4.500.000
• Pentru 31 puncte, 4.500.000 < B ≤ 35.000.000
• Pentru 25 puncte, nu există alte restricții

Exemplul 1

triprime.in

1 50

triprime.out

2

Explicație

Sunt două numere triprime de la 1 la 50: 30 = 2 × 3 × 5 și 42 = 2 × 3 × 7.

Exemplul 2

triprime.in

10 5

triprime.out

Datele sunt invalide

Rezolvare

<syntaxhighlight lang="python" line>

1. 4139 triprime

def sieve_of_eratosthenes(n):

 primes = [True] * (n + 1)
 primes[0], primes[1] = False, False
 p = 2
 while p * p <= n:
   if primes[p] == True:
     for i in range(p * p, n + 1, p):
       primes[i] = False
   p += 1
 return [i for i in range(n + 1) if primes[i]]

def count_triprimes_in_interval(A, B):

 primes = sieve_of_eratosthenes(B)
 count = 0
 for num in range(A, B + 1):
   prime_factors = [p for p in primes if num % p == 0]
   if len(prime_factors) == 3:
     count += 1
 return count

def is_valid_input(A, B):

 if not (1 <= A <= B <= 390_000_000):
   return False
 return True

def main():

 with open("triprime.in", "r") as f:
   A, B = map(int, f.readline().split())
   
 if not is_valid_input(A, B):
   with open("triprime.out", "w") as f:
       f.write("Datele sunt invalide")
   return

 triprime_count = count_triprimes_in_interval(A, B)

 with open("triprime.out", "w") as f:
   f.write(str(triprime_count))

if __name__ == "__main__":

 main()

</syntaxhighlight>