E. SAMEPAIR

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Nguồn: Beginner Free Contest 6

Hai số nguyên dương A B được gọi là một cặp số tương đồng nếu như chúng có chung tập các ước nguyên tố. Ví dụ: 12 18 là cặp số tương đồng vì có chung tập ước nguyên tố là \{2, 3\} . Cho trước hai số nguyên dương L R , hãy đếm số lượng cặp tương đồng A B L ≤ A < B ≤ R .

Dữ liệu vào:

  • Gồm một dòng duy nhất chứa hai số nguyên dương L R (L < R ≤ 10^6) .

Dữ liệu ra:

  • In ra kết quả bài toán.

Ví dụ:

Dữ liệu vào:
1 10

Dữ liệu ra:

4
Giải thích:
  • 4 cặp số tương đồng đó là: \{2, 4\}, \{2, 8\}, \{3, 9\}, \{4, 8\} .

Giới hạn:

  • 60\% số test có R − L ≤ 1000 ;
  • 40\% số test còn lại không giới hạn gì thêm.