Đếm số nguyên tố

Xem PDF
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


  • 0
    bin9638    9:42 a.m. 14 Tháng 8, 2020

    sàng bình thường không acc đâu nhé.


    • 0
      N7hoatt    3:24 p.m. 14 Tháng 8, 2020

      bài dùng sàng gì cho đủ ac a


    • 0
      hhoangcpascal    10:12 a.m. 14 Tháng 8, 2020

      Sài Atkin thử và mém TLE :V


      • 0
        SPyofgame    9:30 p.m. 26 Tháng 9, 2021

        Anh có thể xem atkin của em UwU -> Sieve benchmark


        • 0
          bin9638    10:15 a.m. 14 Tháng 8, 2020

          Hình như đa số trường hợp atkin chạy thua sàng eratos phải k nhỉ ((


          • 0
            SPyofgame    9:31 p.m. 26 Tháng 9, 2021

            Về lí thuyết thì có rất nhiều tiềm năng đê Atkin Sieve vượt mặt Erastothenes Sieve

            Nhưng mà rất khó phức tạp để tối ưu, và cái khó nữa là mỗi lần tối ưu thêm một số phương trình hay wheel sieve thì những cái lookup-table để boost cũng khó để xây tiếp 🙁


            • 0
              hhoangcpascal    10:23 a.m. 14 Tháng 8, 2020

              Đúng rồi 😊 vì xét nhiều, với lại còn nhiều nhân


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

                Phép nhân có thể giảm được anh. Modulo free cũng được


          • 0
            algorit    9:59 a.m. 14 Tháng 8, 2020

            Đơn nhiên rồi , dùng sàng O(n/6 + log(n)) thì ăn ngay ấy mà =))

          5 bình luận nữa