Đếm số nguyên tố

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
bin9638
Dạng bài
Điểm: 400 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hôm nay coder bin9638 top 1 thế giới nhận lời thách đấu của coder thứ 7 tỉ thế giới algorit solo giải 1 bài toán do giáo sư nhphucqt đưa ra.

Bài toán là cho 2 số tự nhiên \(l,r\). Hãy đếm số lượng số nguyên tố giữa chúng.

bin9638 loay hoay mãi mà vẫn chưa nghĩ ra cách làm trong khi algorit đã sắp xong, các bạn hãy giúp bin9638 chiến thắng trong cuộc solo này nhé. Nếu giải được thì bin9638 sẽ chia 1 nửa phần thưởng của cuộc solo này cho các bạn đó !

- Yêu cầu: đếm số lượng số nguyên tố trong đoạn \([l,r]\)

Input

  • Dòng đầu tiên chứa số nguyên dương \(q\) là số đoạn \([l,r]\)
  • \(q\) dòng tiếp theo mỗi dòng chứa \(2\) số nguyên dương \(l\) và \(r\)

Output

  • Gồm \(q\) dòng, dòng thứ \(i\) ghi một số là số các số nguyên tố trong đoạn \([l,r]\) thứ \(i\) đã cho.

Constraints

  • \(1 \leq l,r \leq 2 \times 10^8\)
  • \(1 \leq q \leq 10^5\)

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(q \leq 10^3\), \(l\) và \(r \leq 10^7\)
  • Subtask \(2\) (\(50\%\) số điểm): \(q \leq 10^5\), \(l\) và \(r \leq 2 \times 10^8\)

Example

Test 1

Input 
1
2 5
Output 
3

Bình luận


  • 2
    VoBaThongL921    10:25 a.m. 25 Tháng 9, 2021 ← đã chỉnh sửa

    sau bao nỗ lực tránh rte và ole, mình nhận ra sàng thường nhưng cải tiến 6k +- 1 là ac:))


    • 2
      SPyofgame    9:35 p.m. 26 Tháng 9, 2021

      Bạn muốn cải tiến thêm mà không quá phức tạp thì có thể xem ở đây nhé UwU Sieving Benchmark


      • 2
        VoBaThongL921    6:59 a.m. 27 Tháng 9, 2021

        được idol rep luôn:) cảm ơn anh OwO


        • 2
          SPyofgame    11:51 a.m. 2 Tháng 10, 2021

          idol gì thằng gà như mình hả bạn 🙁


          • 2
            VoBaThongL921    1:10 p.m. 2 Tháng 10, 2021

            Thôi anh ơi khiêm tốn quá đâu có tốt:>


            • 4
              SPyofgame    2:57 p.m. 3 Tháng 10, 2021

              Theo anh thấy thì áp dụng thuyết tương đối của Einstein ta có số người có quan điểm rằng anh gà cao hơn nhiều OwO


              • 2
                VoBaThongL921    4:31 p.m. 3 Tháng 10, 2021

                Nói chuyện với idol đau đầu qué:) Thuyết tương đối của Einstein là gì vậy ạ, em ngu hóa học nên không biết ạ:<


                • 2
                  ap    9:34 a.m. 28 Tháng 11, 2021

                  lý mà:)


                  • 3
                    VoBaThongL921    9:38 a.m. 28 Tháng 11, 2021

                    burh điểm lý tôi 2.0 có vấn đề zì ko:((


                    • -3
                      dattuan16_05_07    3:45 p.m. 10 Tháng 3, 2022

                      sao bữa tôi hỏi ông hs gì thì ông bảo giỏi mà sao lại 2.0 lí đc(.___.)


                      • -3
                        NMK_hacker_123    4:02 p.m. 10 Tháng 3, 2022

                        thì do mấy con 15' miệng hay giữa kì kéo con 2 lên đc đtb 6,6 :))


                      • -2
                        Nguyễn_Minh_Khang21L7    8:01 p.m. 30 Tháng 11, 2021 ← đã chỉnh sửa

                        ah Thông 2 điểm lý à :))

        5 bình luận nữa