DCP-577: Exactly L prime numbers Back to All Problems

Hard Search Techniques > Binary Search/Bisection


You are given a number **N**. Find the number of pairs **(L, R)** possible, where **1 <= L <= R <= N** such that there are exactly **L prime numbers** between L to R. For N = 4, possible pairs are [ {1, 2}, {2, 3}, {2, 4} ]. Input: ------ Input starts with an integer **T (1<=10^5)**, denoting the number of test cases. Each case contains an integer **N (1 ≤ N ≤ 10^6)** denoting the number. Output: ------- For each test case, print the result. Sample Input ------------ 1 4 Sample Output ------------- 3


Problem Setter:

Bir Bahadur Khatri

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

34/97

Solve/Submission

Ranking

# User Language Timing
01 Morass Cpp14 0.03s
02 yead_025 Cpp 0.04s
03 feodorv C 0.07s
04 rayhan50001 Cpp14 0.07s
05 Limon_88 Cpp14 0.08s
06 durlov1234 Cpp 0.10s
07 sayedgkm Cpp14 0.12s
08 mir003 Cpp 0.13s
09 mh755628 Cpp14 0.13s
10 RHT_20 Cpp 0.14s
11 mdnaeemalimran Cpp 0.16s
12 AlaminJust Cpp 0.19s
13 shahjalalshohag Cpp14 0.22s
14 Faizul_BU Cpp14 0.23s
15 njrafi Cpp 0.24s
16 rezaulhsagar Cpp 0.24s
17 MathProgrammer Cpp 0.26s
18 emrul Cpp 0.30s
19 fayedanik Cpp 0.31s
20 nahid08 Cpp 0.34s
21 CLown1331 Cpp14 0.35s
22 prodipdatta7 Cpp14 0.37s
23 _c_k_r_ Cpp14 0.41s
24 inam Cpp14 0.43s
25 dmehrab06 Cpp14 0.64s
26 badassiumoxide Cpp 0.64s
27 shamimjucse Cpp 0.78s
28 somia Cpp 0.82s
29 Old_kernel Cpp14 0.86s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support