Pracsiu Dan (dnprx) 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
50 105
triprime.out
5
Explicație
Sunt cinci numere triprime de la 50 la 105: 66 = 2 × 3 × 11, 70 = 2 × 5 × 7, 78 = 2 × 3 × 13, 102 = 2 × 3 × 17 și 105 = 3 × 5 × 7.
Exemplul 3:
triprime.in
1000 3000
triprime.out
348
Explicație
Sunt 348 de numere triprime în intervalul [1000, 3000].