Bài 1. Số nguyên tố (Olympic Mùa Xuân - 2026)

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1000 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong Toán học, số nguyên tố được định nghĩa như sau: "Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có đúng hai ước số dương là 1 và chính nó."

Cho trước hai số nguyên dương \(L, R\) (với \(L, R \leq 10^6\)). Yêu cầu: Hãy đếm số lượng số nguyên tố và tổng các số nguyên tố trong đoạn \([L, R]\) cho trước.

Input

Dòng đầu tiên chứa số nguyên dương \(Q\) là số lượng bộ test cần thực hiện (\(Q \leq 1000\))
\(Q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(L, R\)

Output

Ghi ra \(Q\) dòng, mỗi dòng gồm 2 số nguyên là số lượng số nguyên tố và tổng các số nguyên tố trong đoạn \([L, R]\) tương ứng
Các giá trị trên cùng một dòng cách nhau một khoảng trắng

Example

Test 1

Input

1
1 10

Output

4 17

Note

Các số nguyên tố trong đoạn \([1,10]\) là 2, 3, 5, 7 nên có số lượng là 4 và tổng 17.

Test 2

Input

2
4 17
10 20

Output

5 53
4 60

Note

Các số nguyên tố trong đoạn \([4,17]\) là 5, 7, 11, 13, 17 nên có số lượng là 5 và tổng 53.
Các số nguyên tố trong đoạn \([10,20]\) là 11, 13, 17, 19 nên có số lượng là 4 và tổng 60.

Scoring

Subtask 1 (50% số điểm): \(Q = 1\); \(L, R \leq 10^4\)
Subtask 2 (30% số điểm): \(2 \leq Q \leq 100\); \(L, R \leq 10^6\)
Subtask 3 (20% số điểm): \(100 < Q \leq 1000\); \(L, R \leq 10^6\)

Bình luận (3)

Tải bình luận...