SNGCP - Count Primes
Let num(num >= 0) is a positive integer or zero. We can represent num in the following two forms if it is possible to do so -
1. num = n2 + 2 * n, for non-negative integer n
2. num = m2 - 2 * m, for non-negative integer m
Suppose there is num that can be represented in both the forms. Consider this type of number as a magic number. Consider the following 5 cases -
1. n is the only prime.
2. m is the only prime.
3. n and m both are primes.
4. n is prime.
5. m is prime.
Input
First line of input is t, total number of test cases. For each test case the first line is q, total number of queries. Then there will be (2 * q) lines. First line contains c (referring to case mentioned in the problem description) and second line contains two integers a and b defining the range [a, b] for magic number.
t < 1001
q < 5001
0 < c < 6
minimum_value_of_a = 0
maximum_value_of_b = 106
Output
For every test case, that has q queries, the output has (q + 1) lines. First line will be simply printing the test case number and then q lines will be printing total number of magic numbers in the given range [a, b] under the specific case mentioned in input.
Example
Input: 2
3
1
5 20
2
1 30
3
10 18
2
4
1 10
5
1 10 Output: Test Case :#1:
Query :#1: 1
Query :#2: 1
Query :#3: 1
Test Case :#2:
Query :#1: 1
Query :#2: 1
hide comments
David:
2020-04-09 22:11:56
Additional time required for Java to solve the problem. Start up time for the JVM is more than the allowed time limit. This probably also occurs for interpreted languages. |
|
Scape:
2016-03-26 11:06:12
Lame problem |
|
hodobox:
2016-01-18 22:39:31
Can confirm what Andrey said... beware of a>b. |
|
AvmnuSng:
2013-12-04 14:55:31
@NIK : you need to check arrays, you are using to store values, again. Just correct entries in arrays then AC is no where :) |
|
NIK:
2013-12-04 13:00:06
@Abhimanyu,
|
|
Andrey Maksimenko:
2013-12-01 08:42:51
It is not clear, what is the answer for input:
|
|
(^_^):
2013-11-21 06:41:20
can someone provide me more test cases I am getting wrong answer again and again
|
|
mehmetin:
2013-11-16 11:22:42
You should consider 0 as a magic number. Problem description is wrong, it should say something like "Let num (num>=0) is a positive or zero integer" in the first line of description. It shouldn't be too hard for the problem setter to change it. Last edit: 2013-10-19 16:20:40 |
|
Piyush Kumar:
2013-11-16 11:22:42
What about 0? First line says num>0, and at the bottom it says minimum_value_of_a = 0. Last edit: 2013-10-18 20:22:12 |
Added by: | AvmnuSng |
Date: | 2013-09-21 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Abhimanyu Singh My Problems |