Bài 9.3. Khám Phá Dải Ngân Hà "PrimeSum" - [Độ khó: Khá]


LÀM BÀI

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Bài 9.3. Khám Phá Dải Ngân Hà "PrimeSum" - [Độ khó: Khá]

Bạn là một nhà thám hiểm không gian, được giao nhiệm vụ phân tích các hành tinh trong Dải Ngân Hà "PrimeSum". Mỗi hành tinh được xác định bởi một ID duy nhất là một số nguyên dương. "Chỉ số năng lượng" của một hành tinh được tính bằng tổng các ước nguyên tố phân biệt của ID của nó. Ví dụ, nếu ID là 12, các ước nguyên tố của 12 là 2, 2, 3. Các ước nguyên tố phân biệt là 2 và 3, nên chỉ số năng lượng là 2 + 3 = 5. Nếu ID là 7, ước nguyên tố phân biệt là 7, chỉ số năng lượng là 7.

Bạn cần tính tổng chỉ số năng lượng của tất cả các hành tinh có ID trong một khoảng từ L đến R (bao gồm cả LR).

INPUT FORMAT

Một dòng duy nhất chứa hai số nguyên LR (1 <= L <= R <= 10^6).

OUTPUT FORMAT

In ra một số nguyên duy nhất là tổng chỉ số năng lượng của tất cả các hành tinh trong khoảng từ L đến R.

Ví dụ:

Input:

10 15

Output:

42

Giải thích:

  • ID = 10: Ước nguyên tố phân biệt: 2, 5. Chỉ số năng lượng: 2 + 5 = 7.
  • ID = 11: Ước nguyên tố phân biệt: 11. Chỉ số năng lượng: 11.
  • ID = 12: Ước nguyên tố phân biệt: 2, 3. Chỉ số năng lượng: 2 + 3 = 5.
  • ID = 13: Ước nguyên tố phân biệt: 13. Chỉ số năng lượng: 13.
  • ID = 14: Ước nguyên tố phân biệt: 2, 7. Chỉ số năng lượng: 2 + 7 = 9.
  • ID = 15: Ước nguyên tố phân biệt: 3, 5. Chỉ số năng lượng: 3 + 5 = 8. Tổng chỉ số năng lượng từ 10 đến 15 là 7 + 11 + 5 + 13 + 9 + 8 = 42. (Gợi ý: Có thể sử dụng Sàng Eratosthenes để tìm các ước nguyên tố cho tất cả các số trong phạm vi hiệu quả.)


Comments

There are no comments at the moment.

Zalo