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

#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()