FRQPRIME - Frequent Prime Ranges
A range [L..H] is called a K-Frequent Prime range if there are at least K primes amongst the numbers L, L+1, ... H. Given N and K, calculate how many subranges of the range [2..N] are K-Frequent Prime.
Input
The first line contains the number of test cases T. Each of the next T lines contains 2 integers N and K.
Output
Output T lines, one corresponding to each test case, containing the required answer.
Constraints
1 <= T <= 100
2 <= N <= 100000
0 <= K <= 10000
Example
Input: 4 2 1 5 2 5 1 9 3 Output: 1 4 9 8
Explanation
Note: For the first test case, the only valid subrange is [2..2], whereas for the second test case, the valid subranges are: [2..3], [2..4], [2..5], [3..5].
hide comments
kp:
2015-06-19 14:35:07
use long for answer ! 1 WA :( |
|
Sudarshan K:
2014-12-27 09:38:28
Super problem. :) No need for using extra memory. Binary Search is beautiful :) |
|
Daga:
2014-10-08 00:18:30
Enjoyed
|
|
Arvind:
2014-10-01 11:25:09
Awesome Problem ... Simple Binary Search... Last edit: 2014-10-01 11:25:38 |
|
Massand Sagar Sunil:
2013-06-07 21:07:11
Could you please explain test case 3?Shouldn't the answer be 8?
|
|
vimal raj sharma old account:
2010-02-19 17:40:21
@ Siarhei Khamenka
|
|
Siarhei Khamenka:
2010-02-19 13:31:21
got the same, but did you test K=0 ? |
Added by: | Varun Jalan |
Date: | 2010-01-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | own problem used for Technovanza |