Cristina94: Pagină nouă: ==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 num...

2024-03-28T10:06:26Z

Pagină nouă: ==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 num...

New page

==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>

4139 - triprime - Revision history