{"code":"cntprime","name":"Đếm số nguyên tố","description":"Hôm nay coder [user:bin9638] top 1 thế giới nhận lời thách đấu của coder thứ 7 tỉ thế giới [user:algorit] solo giải 1 bài toán do giáo sư [user:nhphucqt] đưa ra.\r\n\r\nBà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.\r\n\r\n[user:bin9638] loay hoay mãi mà vẫn chưa nghĩ ra cách làm trong khi [user:algorit] đã sắp xong, các bạn hãy giúp [user:bin9638] chiến thắng trong cuộc solo này nhé. Nếu giải được thì [user:bin9638] sẽ chia 1 nửa phần thưởng của cuộc solo này cho các bạn đó !\r\n\r\n**- Yêu cầu:** đếm số lượng số nguyên tố trong đoạn $[l,r]$\r\n\r\n#### Input\r\n\r\n+ Dòng đầu tiên chứa số nguyên dương $q$ là số đoạn $[l,r]$\r\n+ $q$ dòng tiếp theo mỗi dòng chứa $2$ số nguyên dương $l$ và $r$\r\n\r\n#### Output\r\n- 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.\r\n\r\n#### Constraints\r\n+ $1 \\leq l,r \\leq 2 \\times 10^8$\r\n+ $1 \\leq q \\leq 10^5$\r\n\r\n#### Scoring\r\n+ Subtask $1$ ($50\\%$ số điểm): $q \\leq 10^3$, $l$ và $r \\leq 10^7$\r\n+ Subtask $2$ ($50\\%$ số điểm): $q \\leq 10^5$, $l$ và $r \\leq 2 \\times 10^8$\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        1\r\n        2 5 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        3\r\n        ```","points":400.0,"partial":true,"time_limit":2.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}