Các số gần nguyên tố (Almost Prime Numbers)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một số nguyên dương $x$ được gọi là gần nguyên tố nếu $x$ không phải là số nguyên tố và mọi ước nguyên tố của $x$ đều giống nhau.

Nói cách khác, $x$ là số gần nguyên tố khi và chỉ khi tồn tại một số nguyên tố $p$ và một số nguyên $k\ge2$ sao cho

Ví dụ:

• $4=2^2$, $8=2^3$, $9=3^2$ là các số gần nguyên tố;
• $6=2\cdot3$ không phải số gần nguyên tố vì có hai ước nguyên tố khác nhau;
• $5$ không phải số gần nguyên tố vì chính nó là số nguyên tố.

Cho hai số nguyên low và high. Hãy đếm số lượng số gần nguyên tố $x$ nằm trong đoạn đóng

Input

Dòng duy nhất chứa hai số nguyên low và high.

Output

In một số nguyên: số lượng số gần nguyên tố thuộc đoạn $[low,high]$.

Subtask

• Subtask 1 — 20%: $1\le low\le high\le10^6$.
• Subtask 2 — 30%: $1\le low\le high\le10^9$.
• Subtask 3 — 50%: $1\le low\le high<10^{12}$.

Ví dụ

Input

1 10

Output

3

Giải thích

Trong đoạn $[1,10]$ có đúng ba số gần nguyên tố:

Vì vậy đáp án là $3$.