View source for 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>
#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>