Rezolvare PBinfo #4139

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].