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
vl4deee11:
2024-06-24 06:41:12
use eratosthenesSieve(100000 + 1) ! |
|
vishalshrm539:
2020-10-05 17:06:34
Sieve + Binary Search |
|
smso:
2020-05-22 07:32:25
sieve + prefix sum + brute force |
|
ashok_shaun:
2019-11-12 11:54:29
is binary search "THE OMNIPOTENT"? |
|
sushantgokhale:
2017-04-25 11:32:39
Because I couldnt compute n(n-1)/2 directly, got 7-8 times WA. Disgusting :|
|
|
sushantgokhale:
2017-04-25 10:52:33
@Varun.
|
|
rajeev_899:
2017-03-14 17:11:26
No Need Of Binary Search....Think Simple |
|
shahzada:
2017-03-12 13:24:50
use long long ...costed me 2 WA. |
|
aman224:
2017-02-20 14:45:01
O(pi(N)) , where pi(N) is the number of primes in [2...N]
|
|
Anand:
2017-01-24 07:39:48
not casting n to long while division costed me 4 WA |
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 |